Heap Sort

Idea

Heap Sort leverages a heap: build a max-heap (or min-heap), repeatedly take the top element to the end, adjust the remaining heap, and continue until sorted.

Algorithm

1. Build a max-heap from the array.
2. Swap heap top (max) with the last element; heap size minus 1.
3. Heapify the remaining elements.
4. Repeat steps 2–3 until one element remains.

Pseudo-code:

function heapSort(A, n):
    buildMaxHeap(A, n)
    for i = n-1 downto 1:
        swap(A[0], A[i])
        heapify(A, 0, i)

function buildMaxHeap(A, n):
    for i = n/2-1 downto 0:
        heapify(A, i, n)

function heapify(A, i, n):
    largest = i
    l = 2*i+1
    r = 2*i+2
    if l < n and A[l] > A[largest]:
        largest = l
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        swap(A[i], A[largest])
        heapify(A, largest, n)

Definition and Properties of a Heap

• A heap is a complete binary tree, stored in an array
• Max-heap: the value of every node is greater than or equal to its children, so the top holds the maximum
• Min-heap: the value of every node is less than or equal to its children, so the top holds the minimum
• The left child of node $i$ is $2i+1$, the right child is $2i+2$, and the parent is $\lfloor (i-1)/2 \rfloor$

Code Implementation

// Adjust the subtree rooted at i so that it becomes a max-heap
void Heapify(int A[], int i, int n) {
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && A[l] > A[largest]) largest = l;
    if (r < n && A[r] > A[largest]) largest = r;
    if (largest != i) {
        int tmp = A[i]; A[i] = A[largest]; A[largest] = tmp;
        Heapify(A, largest, n);  // adjust the subtree recursively
    }
}

// Build the heap: start from the last non-leaf node and sift down
void BuildMaxHeap(int A[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        Heapify(A, i, n);
}

// Heap sort
void HeapSort(int A[], int n) {
    BuildMaxHeap(A, n);
    for (int i = n - 1; i > 0; i--) {
        int tmp = A[0]; A[0] = A[i]; A[i] = tmp;  // move the top (max) to the end
        Heapify(A, 0, i);                          // adjust the remaining part
    }
}

Heap Sort and Priority Queues

The heap is the most common implementation of a priority queue: enqueueing (insertion) costs $O(\log n)$ and dequeueing (taking out the maximum or the minimum) costs $O(\log n)$. Dijkstra’s algorithm, task scheduling, and Top K problems all make use of the heap.

Complexity

• Best/worst/avg: $O(n\log n)$
• Space: $O(1)$
• Stability: unstable

Exercises

Exercise 1

For $A = [4, 10, 3, 5, 1]$, show the initial heap and the state after the first swap.

Exercise 2

What are heap sort’s time and space complexities?