How Heap Sort Works: Explanation and Example

Heap sort works by first building a max heap from the input data, which organizes the largest element at the root. Then, it repeatedly swaps the root with the last element, reduces the heap size, and restores the heap property until the array is sorted.

Syntax

Heap sort involves two main steps: building a max heap and then sorting by extracting the maximum element repeatedly.

• Build Max Heap: Rearrange the array so that it satisfies the max heap property.
• Heapify: Adjust the heap to maintain the max heap property after swaps.
• Sort: Swap the root (max element) with the last element and reduce heap size.

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)

    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

Example

This example shows heap sort sorting an unsorted list of numbers. It builds the max heap, then sorts the list in ascending order.

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]

Common Pitfalls

Common mistakes when implementing heap sort include:

• Not building the max heap correctly before sorting.
• Failing to call heapify after each swap to maintain heap property.
• Mixing up zero-based indexing when calculating child nodes.
• Confusing max heap with min heap, which changes sorting order.

Always remember the heap property: parent nodes are greater than their children in a max heap.

python

def wrong_heapify(arr, n, i):
    # Incorrectly swaps without checking children
    arr[i], arr[0] = arr[0], arr[i]

# Correct heapify is needed to maintain heap property after swaps

Quick Reference

Heap Sort Steps:

• Build a max heap from the input array.
• Swap the root (largest) with the last element.
• Reduce heap size by one.
• Heapify the root to maintain max heap.
• Repeat until heap size is 1.

Key Takeaways

Heap sort uses a max heap to efficiently find and remove the largest element repeatedly.

Building the max heap is the first crucial step before sorting.

Heapify maintains the heap property after each swap during sorting.

Heap sort has a time complexity of O(n log n) and sorts in place without extra memory.

Common errors include incorrect heap construction and forgetting to heapify after swaps.