Heap Sort is a highly efficient comparison-based sorting algorithm that uses a special data structure called a **Binary Heap** to organize elements. It effectively divides the input into a sorted and an unsorted region, much like Selection Sort, but it uses the heap structure to find the maximum element much faster.

Imagine a "King of the Hill" tournament. You start with a chaotic group of players. You organize them into a bracket (a tree) where every parent must be stronger than their children. Once organized, the strongest player is naturally at the very top (the root). You take that winner out and place them in the "Winner's Circle" (the sorted array). You then take the last person in the bracket, move them to the top, and have them compete downwards until the next strongest player rises to the top. Repeating this ensures everyone leaves the bracket in perfect order of strength.

The algorithm relies on the **Max Heap Property**: in a binary tree, every parent node must be greater than or equal to its children.

• Build Heap: First, we transform the unsorted array into a Max Heap. This ensures the largest element is at index 0.
• Swap: We swap the first element (largest) with the last element of the unsorted region. The largest item is now "sorted" at the end of the array.
• Heapify: The new root element (which we just moved from the bottom) is likely small and violates the Max Heap property. We "bubble it down" (heapify) to its correct position to restore the heap.
• Repeat: We reduce the size of the "unsorted" heap by one and repeat the process until the heap is empty.

Let's trace the algorithm on a small array.

Below is the implementation of Heap Sort in multiple programming languages.

#include <stdio.h>
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;
        heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // Extract elements from heap one by one
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    heapSort(arr, n);
    
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Heap Sort is consistent and reliable, offering good performance without the memory overhead of Merge Sort.

Time Complexity

Space Complexity

Heap Sort is the preferred choice in constrained environments.