Heap Fundamentals

Heap sort is a tree-based selection algorithm that treats records as a complete binary tree stored sequentially in memory. The algorithm leverages the intrinsic relationship between parent and child nodes to find the maximum or minimum key value from an unordered sequence.

Heaps come in two varieties: max-heap and min-heap. A max-heap maintains the largest element at the root, with all child nodes smaller than their parent. Conversely, a min-heap positions the smallest element at the root, with all children larger than their parent.

The time complexity of heap sort is O(n×logn), though it is classified as an unstable sorting algorithm.

Implementing heap sort requires solving two core problems:

1. Building a heap from a unordered array

2. Reconstructing the heap after removing the root element

Heapify Algorithm

The core operation is a downward adjustment that ensures the heap property is maintained. This approach assumes the left child is smaller enitially, then verifies and adjusts as needed.

void heapify(int* arr, int length, int index)
{
    int child = 2 * index + 1;
    
    while (child < length)
    {
        // Select the smaller child
        if (child + 1 < length && arr[child + 1] < arr[child])
        {
            child++;
        }
        
        // Swap if child is smaller than parent
        if (arr[child] < arr[index])
        {
            swap(&arr[child], &arr[index]);
            index = child;
            child = 2 * index + 1;
        }
        else
        {
            break;
        }
    }
}

Complete Heap Sort Implementation

void heapSort(int* arr, int size)
{
    // Build the initial min-heap
    // Start from the last non-leaf node
    for (int i = (size - 2) / 2; i >= 0; i--)
    {
        heapify(arr, size, i);
    }
    
    // Extract elements from heap one by one
    int end = size - 1;
    while (end > 0)
    {
        // Move current root (minimum) to end
        swap(&arr[0], &arr[end]);
        
        // Restore heap property for remaining elements
        heapify(arr, end, 0);
        
        end--;
    }
}

Building the Initial Heap

The first phase constructs a valid heap from an unsorted array. Starting from the last non-leaf node—which has index (size-2)/2—we apply the heapify operation working backward to the root. This ensures that after processing all nodes, the array satisfies the heap property.

For a descending sort, we build a min-heap since we want the smallest element at the root. For ascending order, construct a max-heap instead.

The heapify function employs a greedy assumption strategy. The while loop continues until reaching a leaf node. Within each iteration, we first determine which child is smaller by checking if the right child exists and comparing it with the left child. If the smaller child is less than the parent, we swap them and continue the downward traversal with updated indices.

Extracting Sorted Elements

Once the initial heap is built, the extraction phase begins. We repeatedly swap the root element with the last unsorted position, then reduce the heap size by one and restore the heap property. This process places the smallest element at the array's end, then the next smallest, and continues until the entire array is sorted.

The end-- statement prevents already-placed elements from participating in subsequent heap operations, ensuring they remain in their final positions.

The algorithm efficiently sorts the array in descending order by leveraging the heap structure to repeatedly locate and place the minimum remaining value.