Oct 6, 2019 · Oct 2, 2019 · Oct 2, 2019 · Oct 6, 2019
diff --git a/allalgorithms/sorting/__init__.py b/allalgorithms/sorting/__init__.py
 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
 # -*- 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
 # 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
    stooge_sort,
    cocktail_shaker_sort,
    tree_sort,
    heap_sort,
    shell_sort,
 )


    def test_cocktail_shaker_sort(self):
        self.assertEqual([-44, 1, 2, 3, 7, 19], cocktail_shaker_sort([7, 3, 2, 19, -44, 1]))

    deftree_sort(self):

    deftest_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]))
Original file line number	Diff line number	Diff line change
Expand Up		@@ -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
Original file line number	Diff line number	Diff line change
		@@ -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)
Original file line number	Diff line number	Diff line change
		@@ -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
Original file line number	Diff line number	Diff line change
Expand Up		@@ -9,6 +9,7 @@
		stooge_sort,
		cocktail_shaker_sort,
		tree_sort,
		heap_sort,
		shell_sort,
		)

Expand All		@@ -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]))

		deftree_sort(self):

		deftest_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]))

Expand Down