Heap Sort Implementation

Problem Statement

Sort an array using heap sort: turn the array into a max-heap, then repeatedly swap the root (maximum) with the last element and restore the heap on the shrinking prefix.

Example

Input:  [4, 10, 3, 5, 1]
Build max-heap -> extract max repeatedly
Output: [1, 3, 4, 5, 10]

Approach

First heapify the array bottom-up (O(n)). Then, n-1 times, swap the root with the current last slot and sift the new root down over the reduced heap. Heap sort gives a guaranteed O(n log n) with O(1) extra space, though it is not cache-friendly or stable.

Complexity

• Time: O(n log n) in all cases
• Space: O(1)

Solution Code

Python

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        _heapify(arr, n, i)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        _heapify(arr, end, 0)
    return arr

def _heapify(arr, n, i):
    largest, l, r = i, 2 * i + 1, 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        _heapify(arr, n, largest)

Java

void heapify(int[] arr, int n, int i) {
    int largest = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
        heapify(arr, n, largest);
    }
}
void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    for (int end = n - 1; end > 0; end--) {
        int t = arr[0]; arr[0] = arr[end]; arr[end] = t;
        heapify(arr, end, 0);
    }
}

C++

void heapify(vector<int>& arr, int n, int i) {
    int largest = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    for (int end = n - 1; end > 0; end--) {
        swap(arr[0], arr[end]);
        heapify(arr, end, 0);
    }
}

Key Takeaways

• Heap sort guarantees O(n log n) with O(1) extra space.
• Building the heap bottom-up is O(n), not O(n log n); it is not stable.
• Reference: CLRS, Ch. 6; Wikipedia, "Heapsort".