Heap Sort

function heapSort(arr) {
    const n = arr.length;

    // Build max heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements from heap one by one
    for (let i = n - 1; i > 0; i--) {
        // Move current root to end
        [arr[0], arr[i]] = [arr[i], arr[0]];

        // Call heapify on reduced heap
        heapify(arr, i, 0);
    }
    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // If largest is not root
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

How Heap Sort Works

Heap Sort uses the properties of a binary heap to sort elements. A binary heap is a complete binary tree where each parent node is larger (max heap) or smaller (min heap) than its children.

Algorithm Steps:

1. Build Max Heap: Convert array into a max heap structure
2. Extract Maximum: Swap root (maximum) with last element
3. Reduce Heap Size: Exclude the sorted element from heap
4. Heapify: Restore heap property for remaining elements
5. Repeat: Continue until all elements are sorted

Heap Data Structure:

• Complete Binary Tree: All levels filled except possibly the last
• Max Heap Property: Parent ≥ Children (for ascending sort)
• Array Representation: Easy to implement using arrays
• Efficient Operations: O(log n) insertions and deletions

Key Characteristics:

• In-place: Requires only constant extra space O(1)
• Unstable: Does not maintain relative order of equal elements
• Guaranteed Performance: Always O(n log n) in worst case
• Not adaptive: Same performance regardless of input order

Advantages:

• Predictable performance: Always O(n log n) worst case
• In-place sorting: No additional space required
• Simple implementation: Based on well-understood heap structure
• Good for large datasets: Consistent performance scaling

When to Use Heap Sort:

• Guaranteed performance needed: When worst-case O(n log n) is required
• Memory constrained: When additional O(n) space isn't available
• Simple implementation: When code simplicity is preferred
• Large datasets: When consistent performance is more important than average-case speed