Heap Sort Algorithm

Heap Sort uses a binary heap to repeatedly move the largest element to the end of the array, producing an in-place sorted result.

What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that uses a binary heap. For ascending order, it first builds a max heap, where every parent is greater than or equal to its children.

Once the array is a max heap, the largest element is always at the root. Heap Sort swaps the root with the last element, shrinks the heap, and restores the heap property using heapify.

Core Intuition

Heap Sort is built around a simple idea: if we can always access the largest element quickly, we can place that element at the end of the array and repeat.

A max heap gives us exactly that. The largest element is at index 0. After moving it to the end, we repair the remaining heap so the next largest element rises to the root.

Heap Representation in an Array

A binary heap is often visualized as a tree, but it is stored inside an array. This is why Heap Sort can work in place without creating a separate tree structure.

Counting Sort Algorithm Steps

1. Build a max heap.
   Rearrange the array so every parent is greater than or equal to its children.
2. Swap the root with the last heap element.
   The root contains the largest value, so it belongs at the end.
3. Shrink the heap size.
   The last element is now sorted and should no longer be part of the heap.
4. Heapify the root.
   Restore the max heap property for the remaining unsorted region.
5. Repeat extraction.
   Continue until the heap size becomes 1.
6. Return the array.
   The sorted region grows from right to left until the whole array is sorted.

Interactive Heap Sort Visualization

Use the visualization below to see the same heap in two forms: the array representation and the tree representation. Heap Sort repeatedly extracts the root, moves it to the sorted region, and heapifies the remaining heap.

Dry Run Example

Suppose we want to sort:

[4, 10, 3, 5, 1]

Step 1: Build the max heap

• Start heapifying from the last non-leaf node.
• For 5 elements, the last non-leaf index is n // 2 - 1 = 1.
• Heapify index 1, then index 0.
• After building the max heap → [10, 5, 3, 4, 1]

Step 2: Extract the largest element

• The largest element is at the root: 10.
• Swap it with the last element → [1, 5, 3, 4, 10]
• Now 10 is fixed in the sorted region.

Step 3: Heapify the remaining heap

• Heap size is now 4.
• Heapify index 0 to restore the max heap property.
• After heapify → [5, 4, 3, 1, 10]

Continue extraction

• Swap 5 with the last heap element → [1, 4, 3, 5, 10]
• Heapify → [4, 1, 3, 5, 10]
• Continue until sorted → [1, 3, 4, 5, 10]

Heap Sort Code in Python

This implementation builds a max heap and repeatedly moves the maximum element to the end of the array.

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

    def heapify(heap_size, root):
        largest = root
        left = 2 * root + 1
        right = 2 * root + 2

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

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

        if largest != root:
            arr[root], arr[largest] = arr[largest], arr[root]
            heapify(heap_size, largest)

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

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

    return arr


print(heap_sort([4, 10, 3, 5, 1]))

Time and Space Complexity

When Should You Use Heap Sort?

Interview Notes and Common Pitfalls

This section highlights what interviewers usually expect you to know about Heap Sort, especially around heapify, heap size, and array-to-tree index mapping.

What interviewers may expect you to know

• Heap Sort uses a max heap for ascending order.
• The largest element is always at index 0 after building the max heap.
• Building a heap takes O(n), not O(n log n).
• Each extraction uses heapify, which takes O(log n).
• The sorted portion grows from the end of the array.
• Heap Sort is in-place but not stable.

Common mistakes

• Using min heap for ascending Heap Sort without adjusting the logic.
• Forgetting to reduce heap size after moving the max element to the end.
• Using incorrect child index formulas.
• Heapifying from index 0 while building the heap instead of starting from the last non-leaf node.
• Claiming build heap is O(n log n) instead of O(n).
• Calling Heap Sort stable.

Related coding interview problems

• Sort an Array
• Kth Largest Element in an Array
• Top K Frequent Elements
• Find Median from Data Stream
• Merge k Sorted Lists

Quick Quiz

Key Takeaways

• Heap Sort uses a binary heap to sort an array.
• For ascending order, it builds a max heap.
• The largest element is repeatedly swapped to the end.
• Building the heap takes O(n).
• Overall time complexity is O(n log n).
• Heap Sort is in-place but not stable.