Added Heap sort, tests, and documentation. (#36)

abranhe · web-flow · commit 78d8a9bffc97 · 2019-10-05T22:57:34.000-04:00
Added Heap sort, tests, and documentation.

Co-authored-by: Abraham Hernandez &lt;abraham@abranhe.com&gt;
diff --git a/allalgorithms/sorting/__init__.py b/allalgorithms/sorting/__init__.py
@@ -6,3 +6,4 @@
 from .stooge_sort import stooge_sort
 from .cocktail_shaker_sort import cocktail_shaker_sort
 from .tree_sort import tree_sort
+from .heap_sort import heap_sort
diff --git a/allalgorithms/sorting/heap_sort.py b/allalgorithms/sorting/heap_sort.py
@@ -0,0 +1,48 @@
+# -*- coding: UTF-8 -*-
+#
+# Heap Sort Algorithm
+# The All ▲lgorithms library for python
+#
+# Contributed by: DatHydroGuy
+# Github: @DatHydroGuy
+#
+
+
+def build_heap(array_to_sort, array_length, index):
+    """
+    Build a heap, where each node has two child nodes, and a root node is greater than both child nodes.
+    """
+    largest = index         # Flag the largest element as the last (root) element
+    left = 2 * index + 1    # Calculate index of left child node
+    right = 2 * index + 2   # Calculate index of right child node
+
+    # See if left child of root exists and is greater than root
+    if left < array_length and array_to_sort[index] < array_to_sort[left]:
+        largest = left
+
+    # See if right child of root exists and is greater than root
+    if right < array_length and array_to_sort[largest] < array_to_sort[right]:
+        largest = right
+
+    # If a larger element than root was found, swap with root so that root holds the new largest value
+    if largest != index:
+        array_to_sort[index], array_to_sort[largest] = array_to_sort[largest], array_to_sort[index]  # swap
+
+        # Re-build the heap under the new largest root node
+        build_heap(array_to_sort, array_length, largest)
+
+
+def heap_sort(array_to_sort):
+    """
+    Builds a max-heap, then continuously removes the largest element and re-builds the heap until sorted
+    """
+    array_length = len(array_to_sort)
+
+    # Build a max-heap to sort the elements into order
+    for index in range(array_length // 2 - 1, -1, -1):
+        build_heap(array_to_sort, array_length, index)
+
+    # One by one extract elements
+    for index in range(array_length - 1, 0, -1):
+        array_to_sort[index], array_to_sort[0] = array_to_sort[0], array_to_sort[index]  # swap
+        build_heap(array_to_sort, index, 0)
diff --git a/docs/sorting/heap-sort.md b/docs/sorting/heap-sort.md
@@ -0,0 +1,33 @@
+# Heap Sort
+
+Heap sort is a comparison-based sorting algorithm which operates on a Binary Heap data structure. It can be regarded as a version of Selection sort which is improved by use of the heap data structure rather than a linear-time search.
+
+Heap sort is typically slower than Quicksort, but it does have a better worst-case scenario of O(n log n).  It is an in-place algorithm, but does not produce a stable sort.
+
+## Install
+
+```
+pip install allalgorithms
+```
+
+## Usage
+
+```py
+from allalgorithms.sorting import heap_sort
+
+arr = [77, 2, 10, -2, 1, 7]
+heap_sort(arr)
+
+print(arr)
+# -> [-2, 1, 2, 7, 10, 77]
+```
+
+## API
+
+### heap_sort(array)
+
+> Performs an in-place sort of the passed-in array
+
+##### Params:
+
+- `array`: Unsorted Array
diff --git a/tests/test_sorting.py b/tests/test_sorting.py
@@ -9,6 +9,7 @@
     stooge_sort,
     cocktail_shaker_sort,
     tree_sort,
+    heap_sort,
     shell_sort,
 )
 
@@ -34,10 +35,15 @@ def test_stooge_sort(self):
 
     def test_cocktail_shaker_sort(self):
         self.assertEqual([-44, 1, 2, 3, 7, 19], cocktail_shaker_sort([7, 3, 2, 19, -44, 1]))
-    
-    def tree_sort(self):
+
+    def test_tree_sort(self):
         self.assertEqual([-44, 1, 2, 3, 7, 19], tree_sort([7, 3, 2, 19, -44, 1]))
 
+    def test_heap_sort(self):
+        array = [7, 3, 2, 19, -44, 1]
+        heap_sort(array)
+        self.assertEqual([-44, 1, 2, 3, 7, 19], array)
+
     def test_shell_sort(self):
         self.assertEqual([-44, 1, 2, 3, 7, 19], shell_sort([7, 3, 2, 19, -44, 1]))
 
