I've noticed a recurring trend when developers first tackle Heap Sort: they assume that the act of "heapifying" the array is the actual sorting process. You build your max-heap, look at the array, and think, "Okay, it's almost there." But it's not. A max-heap only guarantees that the parent is larger than its children; it doesn't guarantee that the left child is smaller than the right, or that the levels are sorted across.

Take this array: [10, 20, 5, 30, 15]. After you build a max-heap, you might end up with [30, 20, 5, 10, 15]. If you stop there, you haven't sorted anything—you've just ensured the largest element is at the front. To actually sort the array, we have to use that property to our advantage by repeatedly "plucking" the maximum element and moving it to the back of the line.

The Heap is a Tool, Not the Result

The real magic of Heap Sort happens in two distinct phases. First, we organize the raw array into a max-heap. Second, we repeatedly swap the root (the maximum value) with the last element of the current heap, shrink the heap's boundaries, and restore the heap property. I like to think of it as a conveyor belt: we find the biggest item, kick it to the end of the array, and then forget that spot exists so we can find the next biggest item.

Sinking Elements to Maintain Order

Before we can sort, we need a way to "fix" a heap when the root is replaced by a smaller value. We call this heapify. In C, since we are using a zero-indexed array, the left child is always at 2*i + 1 and the right at 2*i + 2. If the parent is smaller than either child, we swap it with the largest child and keep "sinking" that value down until it settles.

void heapify(int arr[], int n, int i) {
    int largest = i; 
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // I'm calling heapify recursively to ensure the 
        // swapped element settles into its correct spot.
        heapify(arr, n, largest);
    }
}

Trading the Root for the Tail

Now that we have heapify, we can implement the actual sort. First, we build the heap by calling heapify on all non-leaf nodes, starting from the bottom up. Then, we enter a loop where we swap the root (index 0) with the last element of the heap, effectively locking the largest element into its final sorted position.

void heapSort(int arr[], int n) {
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

One detail I want you to notice: in the second loop, we pass i as the size to heapify. This is crucial. By decreasing the size, we tell the algorithm to ignore the elements we've already moved to the end. They are "sorted" and should no longer be touched by the heap logic.

📋 Practical Task

Implement Descending Order Heap Sort

Standard Heap Sort uses a max-heap to produce an array sorted in ascending order. Your task is to modify the logic to sort an array in descending order.

To do this, you must implement a min-heap. You will need to create a minHeapify function where the parent is swapped with the smallest of its children, and update the heapSortDescending function to use this new logic.

Requirements:

• Create a function void minHeapify(int arr[], int n, int i).
• Create a function void heapSortDescending(int arr[], int n).
• Test it with the array {12, 11, 13, 5, 6, 7}. The final output should be {13, 12, 11, 7, 6, 5}.