The Algorithms logo
The Algorithms
AboutDonate

Heap Sort

d
D
p
A
H
I
and 7 more contributors
"""
This is a pure Python implementation of the heap sort algorithm.

For doctests run following command:
python -m doctest -v heap_sort.py
or
python3 -m doctest -v heap_sort.py

For manual testing run:
python heap_sort.py
"""


def heapify(unsorted, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index

    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index

    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)


def heap_sort(unsorted):
    """
    Pure implementation of the heap sort algorithm in Python
    :param collection: some mutable ordered collection with heterogeneous
    comparable items inside
    :return: the same collection ordered by ascending

    Examples:
    >>> heap_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]

    >>> heap_sort([])
    []

    >>> heap_sort([-2, -5, -45])
    [-45, -5, -2]
    """
    n = len(unsorted)
    for i in range(n // 2 - 1, -1, -1):
        heapify(unsorted, i, n)
    for i in range(n - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(heap_sort(unsorted))
About this Algorithm

Problem Statement

Given an unsorted array of n elements, write a function to sort the array

Approach

  • Build a max heap from the input data.
  • At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
  • Repeat above steps while size of heap is greater than 1.

Time Complexity

O(n log n) Worst case performance

O(n log n) (distinct keys) or O(n) (equal keys) Best-case performance

O(n log n) Average performance

Space Complexity

O(1) Worst case auxiliary

Example

Input data: 4, 10, 3, 5, 1
        4(0)
       /   \
    10(1)   3(2)
   /   \
5(3)    1(4)

The numbers in bracket represent the indices in the array
representation of data.

Applying heapify procedure to index 1:
        4(0)
       /   \
   10(1)    3(2)
   /   \
5(3)    1(4)

Applying heapify procedure to index 0:
       10(0)
       /  \
    5(1)  3(2)
   /   \
4(3)    1(4)
The heapify procedure calls itself recursively to build heap
in top down manner.

heap-image

Video Explanation

A video explaining the Heap Sort Algorithm