Python Program for Heap Sort with Example and Explanation

Heap sort in Python can be done by building a max heap and then repeatedly swapping the root with the last element and reducing the heap size, as shown in the code: def heap_sort(arr): ... which sorts the list in place.

Examples

Input[3, 1, 4, 1, 5]

Output[1, 1, 3, 4, 5]

Input[10, 7, 8, 9, 1, 5]

Output[1, 5, 7, 8, 9, 10]

Input[]

Output[]

How to Think About It

To sort a list using heap sort, first think of the list as a tree structure. We build a max heap where the largest value is at the root. Then, we swap the root with the last item and reduce the heap size, repeating this until the list is sorted. This way, the largest elements move to the end step by step.

Algorithm

1

Build a max heap from the input list.

2

Swap the root of the heap with the last element.

3

Reduce the heap size by one.

4

Heapify the root to maintain the max heap property.

5

Repeat steps 2-4 until the heap size is 1.

Code

python

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)

Output

[5, 6, 7, 11, 12, 13]

Dry Run

Let's trace the example list [12, 11, 13, 5, 6, 7] through the heap sort code.

1

Build max heap

Start heapifying from index 2 down to 0, resulting in max heap: [13, 11, 12, 5, 6, 7]

2

Swap root with last element

Swap 13 and 7, array becomes [7, 11, 12, 5, 6, 13]

3

Heapify root with reduced size

Heapify root with size 5, array becomes [12, 11, 7, 5, 6, 13]

4

Repeat swap and heapify

Swap 12 and 6, heapify root with size 4, array becomes [11, 6, 7, 5, 12, 13]

5

Continue until sorted

Final sorted array is [5, 6, 7, 11, 12, 13]

Iteration	Array State
Build heap	[13, 11, 12, 5, 6, 7]
Swap root with last	[7, 11, 12, 5, 6, 13]
Heapify root	[12, 11, 7, 5, 6, 13]
Swap root with last	[6, 11, 7, 5, 12, 13]
Heapify root	[11, 6, 7, 5, 12, 13]
Swap root with last	[5, 6, 7, 11, 12, 13]

Why This Works

Step 1: Building the max heap

We start by arranging the list so the largest value is at the root, using heapify from the bottom up.

Step 2: Swapping root with last element

The largest element at the root is swapped with the last element to move it to its correct sorted position.

Step 3: Maintaining heap after swap

After swapping, we call heapify on the root to restore the max heap property for the reduced heap.

Alternative Approaches

Using Python's heapq module (min heap)

python

import heapq

def heap_sort_min(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort_min(arr.copy())
print(sorted_arr)

This uses a min heap and returns a new sorted list but is less efficient for in-place sorting.

Recursive heap sort with explicit max heap build

python

def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

def heap_sort_recursive(arr):
    n = len(arr)
    build_max_heap(arr)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

arr = [4, 10, 3, 5, 1]
heap_sort_recursive(arr)
print(arr)

Separates heap building into a function for clarity, same performance.

Complexity: O(n log n) time, O(1) space

Time Complexity

Heap sort takes O(n) to build the heap and O(log n) for each of the n removals, totaling O(n log n).

Space Complexity

Heap sort sorts the list in place, so it uses only O(1) extra space.

Which Approach is Fastest?

Heap sort is faster than simple sorts like bubble sort but usually slower than quicksort on average; using Python's built-in heapq is simpler but not in-place.

Approach	Time	Space	Best For
Heap Sort (in-place)	O(n log n)	O(1)	Memory efficient sorting
heapq module (min heap)	O(n log n)	O(n)	Simple sorting with new list
Quicksort (not shown)	O(n log n) average	O(log n)	Fast average case sorting