Heap Sort represents a significant optimization over basic selection sort algorithms. The primary limitation of simple selection sort is that after identifying the maximum or minimum element, it performs the next search over the entire unchanged dataset, leading to repeated, inefficient comparisons. Heap Sort, developed by Floyd and Williams in 1964, overcomes this by utilizing the heap data structure.

Core Concepts of Heap Data Structures

Max-Heap and Min-Heap

A heap is a specialized complete binary tree with a specific ordering property:

• Max-Heap: The value of each node is greater than or equal to the values of its child nodes.
• Min-Heap: The value of each node is less than or equal to the values of its child nodes.

Physical and Logical Structure

• Logical Structure: A complete binary tree.
• Physical Structure: Typically implemented using an array.
• Index Relationships: Given a node at index i:
  • Left Child Endex: 2*i + 1
  • Right Child Index: 2*i + 2
  • Parent Index: (i - 1) / 2
• Heap Properties:
  1. Structural Property: The array represents a complete binary tree.
  2. Order Property: Every node's key is the maximum (for max-heap) or minimum (for min-heap) among the keys in its subtree.

Steps for Heap Sort (Ascending Order Example)

1. Heap Construction

Downward Adjustment (Heapify) Algorithm

Prerequisite: The subtrees rooted at the left and right children of the starting node must already satisfy the heap property.

Process: Starting from a given node (often the root after a swap), compare it with its children. If the heap property is violated, swap with the larger child (for max-heap) and continue the process downward until the property is restored or a leaf node is reached.

void exchangeElements(int* elem1, int* elem2) {
    int temp = *elem1;
    *elem1 = *elem2;
    *elem2 = temp;
}

void heapifyDown(int arr[], int heapSize, int startIdx) {
    int currentParent = startIdx;
    int leftChild = currentParent * 2 + 1;

    while (leftChild < heapSize) {
        // Identify the larger child
        int largerChild = leftChild;
        int rightChild = leftChild + 1;
        if (rightChild < heapSize && arr[rightChild] > arr[leftChild]) {
            largerChild = rightChild;
        }
        // Swap if child is larger than parent
        if (arr[largerChild] > arr[currentParent]) {
            exchangeElements(&arr[largerChild], &arr[currentParent]);
            currentParent = largerChild;
            leftChild = currentParent * 2 + 1;
        } else {
            break; // Heap property is satisfied
        }
    }
}

Building the Heap from an Array

A heap is constructed by applying the heapifyDown function in a bottom-up manner, starting from the last non-leaf node.

// Build a max-heap from an unordered array
int totalElements = n; // n is the array size
for (int i = (totalElements - 2) / 2; i >= 0; --i) {
    heapifyDown(arr, totalElements, i);
}

2. Sorting Phase

For ascending order using a max-heap:

1. Swap the root (largest element) with the last element of the heap.
2. Reduce the heap size by one, effectively removing the largest element from the heap.
3. Restore the max-heap property for the new root by calling heapifyDown.
4. Repeat until the heap size is 1.

int lastIdx = n - 1;
while (lastIdx > 0) {
    // Move current max to the end
    exchangeElements(&arr[0], &arr[lastIdx]);
    // Restore heap property for the reduced heap
    heapifyDown(arr, lastIdx, 0);
    --lastIdx;
}

Time Complexity Analysis

• Heap Construction: The bottom-up build process runs in O(n) time, not O(n log n), due to a more precise summation of operations across tree levels.
• Sorting Phase: Each of the (n-1) heapifyDown operations takes O(log n) time.
• Total Complexity: O(n log n).

Complete Implementation Example

#include <stdio.h>

void printArray(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void exchangeElements(int* elem1, int* elem2) {
    int temp = *elem1;
    *elem1 = *elem2;
    *elem2 = temp;
}

void heapifyDown(int arr[], int heapSize, int startIdx) {
    int currentParent = startIdx;
    int leftChild = currentParent * 2 + 1;

    while (leftChild < heapSize) {
        int largerChild = leftChild;
        int rightChild = leftChild + 1;
        if (rightChild < heapSize && arr[rightChild] > arr[leftChild]) {
            largerChild = rightChild;
        }
        if (arr[largerChild] > arr[currentParent]) {
            exchangeElements(&arr[largerChild], &arr[currentParent]);
            currentParent = largerChild;
            leftChild = currentParent * 2 + 1;
        } else {
            break;
        }
    }
}

void heapSort(int arr[], int n) {
    // Phase 1: Build Max-Heap
    for (int i = (n - 2) / 2; i >= 0; --i) {
        heapifyDown(arr, n, i);
    }
    // Phase 2: Extract elements from heap
    int lastIdx = n - 1;
    while (lastIdx > 0) {
        exchangeElements(&arr[0], &arr[lastIdx]);
        heapifyDown(arr, lastIdx, 0);
        --lastIdx;
    }
}

int main() {
    int data[] = { 3, 5, 2, 7, 8, 6, 1, 9, 4, 0 };
    int size = sizeof(data) / sizeof(data[0]);
    heapSort(data, size);
    printArray(data, size);
    return 0;
}