DSA Sorting

Heap Sort

Why guarantee Theta(n log n) without a linear buffer? Because the array itself can be a binary heap, and each extract-max settles one more suffix slot.

Heap sort builds a , then repeatedly swaps root with the end and sifts down. It is , comparison-based, Theta(n log n) worst case, and not .

Algorithm journey

Build max-heap

Heapify from the last parent upward.

Swap root and end

Largest unsettled value becomes final.

Sift down

Restore the heap on the shrunk prefix.

Shrink heap size

Repeat until one element remains.

What actually happens

Naive idea: selection sort with linear scans for each next maximum. Correct, Theta(n^2).

Better idea: a heap answers current maximum in O(1) and restores structure in O(log n).

It still loses to tuned quicksort on many caches, and it is unstable. Prefer mergesort/TimSort when equal-key order matters.

Invariant

After each extract step, the suffix outside the heap is sorted and holds the largest extracted values; the prefix satisfies the max-heap property.

How to choose heap sort

1. Need in-place + hard Theta(n log n)? Heapsort is the classic answer.

2. Need stability? No; use merge/TimSort.

3. Hybrid fallback? Introsort switches to heapsort when quicksort depth goes bad.

Quantitative check

Build-heap is Theta(n). Then n - 1 extracts cost O(log k) on a heap of size k, totaling Theta(n log n). At n = 10^6 you stay in the same asymptotic class as mergesort without a Theta(n) buffer.

Heap Sort Visualizer

Visualizing the Max Heap structure and the sorting process.

Step 0 of -1

Heap

Sorted

Compare

Swap

How it works

Build Max Heap

Transform the input array into a Max Heap data structure. Now the largest item is stored at the root of the heap.

Swap Root with End

Replace the root of the heap with the last item of the heap followed by reducing the size of the heap by 1. This places the largest element at the end of the array (its correct sorted position).

Heapify

"Heapify" the root of the tree. This moves the new root down to its correct position to maintain the Max Heap property.

Repeat

Repeat steps 2 and 3 while the size of the heap is greater than 1.

🔎 Invariants, Trace, and Java Notes

Heap Invariant

During extraction, arr[0..i] remains a valid max heap andarr[i + 1..n - 1] is the sorted suffix. Each root swap grows that suffix by one.

Trace: [4, 10, 3, 5]

Build max heap → [10, 5, 3, 4]
Swap root to end → [4, 5, 3, 10]
Heapify prefix and repeat → [3, 4, 5, 10]

When to Use

Choose Heap Sort when you need in-place O(n log n) worst-case time and do not need stability. In Java, PriorityQueue uses a heap for repeated min/max extraction, while Arrays.sort() uses different tuned algorithms for full sorting.

💻 Implementation

Python

python

def heapify(arr, n, i):
    """
    To heapify subtree rooted at index i.
    n is size of heap
    """
    value = arr[i]
    while 2 * i + 1 < n:
        child = 2 * i + 1
        if child + 1 < n and arr[child] < arr[child + 1]:
            child += 1
        if value >= arr[child]:
            break
        arr[i] = arr[child]
        i = child
    arr[i] = value
 
def heapSort(arr):
    n = len(arr)
 
    # Build a maxheap.
    # Since last parent will be at ((n//2)-1) we can start at that location.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
 
    # One by one extract elements
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]   # swap
        heapify(arr, i, 0)
    
    return arr
 
# Driver code
arr = [12, 11, 13, 5, 6, 7]
print("Sorted array is:", heapSort(arr))
# Output: Sorted array is: [5, 6, 7, 11, 12, 13]

Java

java

public class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;

        // 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);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int arr[], int n, int i) {
        int value = arr[i];
        while (2 * i + 1 < n) {
            int child = 2 * i + 1;
            if (child + 1 < n && arr[child] < arr[child + 1]) child++;
            if (value >= arr[child]) break;
            arr[i] = arr[child];
            i = child;
        }
        arr[i] = value;
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    // Driver code
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Why Floyd heap construction is Θ(n), not Θ(n log n)

leaves

⌈n/2⌉ nodes

Already valid one-node heaps; zero sift work.

Exercises

Show an array of equal keys where one sift-down changes relative order of two equals.
Why is build-heap linear even though each sift-down is O(log n)? Sketch the height-sum argument.
Compare auxiliary space of heapsort vs top-down mergesort on arrays.

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): heapsort and build-heap analysis.
Williams, "Algorithm 232: Heapsort" (CACM, 1964).
Musser, introspective sorting: heapsort as a worst-case guard.

nodes at height h

≤ n / 2^(h+1)

Few nodes can travel many levels.

Exercises

Show an array of equal keys where one sift-down changes relative order of two equals.
Why is build-heap linear even though each sift-down is O(log n)? Sketch the height-sum argument.
Compare auxiliary space of heapsort vs top-down mergesort on arrays.

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): heapsort and build-heap analysis.
Williams, "Algorithm 232: Heapsort" (CACM, 1964).
Musser, introspective sorting: heapsort as a worst-case guard.

total

Σ n·h/2^(h+1) < n

The weighted geometric series is linear.

Exercises

Show an array of equal keys where one sift-down changes relative order of two equals.
Why is build-heap linear even though each sift-down is O(log n)? Sketch the height-sum argument.
Compare auxiliary space of heapsort vs top-down mergesort on arrays.

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): heapsort and build-heap analysis.
Williams, "Algorithm 232: Heapsort" (CACM, 1964).
Musser, introspective sorting: heapsort as a worst-case guard.

Bottom-up sift-down from the last parent exploits this height distribution. Inserting n elements one at a time into an empty heap is O(n log n); Floyd's build is Θ(n). Extraction still costs Θ(n log n), so the complete sort remains Θ(n log n).

Two-region invariant and proof

Before each extraction

a[0:end) is a max heap; a[end:n) is sorted and final, and every suffix element is at least every heap element.

Preservation

The root is the heap maximum. Swapping it to end−1 grows the final suffix; sift-down repairs the only potentially broken root-to-leaf path.

Parent (i−1)/2, left 2i+1, right 2i+2. Iterative sift-down keeps auxiliary space Θ(1); a recursive implementation uses Θ(log n) call-stack space.

Performance profile and adversarial cases

Heap sort performance properties
Property	Behavior	Consequence
Worst-case input	Still Θ(n log n); no pivot attack	Useful as IntroSort's deterministic fallback
Already sorted	Still Θ(n log n), not adaptive	Natural-run sorts can be much faster
Locality	Sift paths jump across the array	Often loses to cache-friendly hybrids despite the same bound
Equal keys	Long-distance swaps break stability	Choose a stable sort when encounter order matters
Input arrangement	No asymptotic best-case speedup	Predictable latency, weaker adaptivity

Test and API checklist

• Empty/singleton/two-element inputs; odd/even heaps and a node with only a left child.
• Sorted, reverse, all equal, duplicates, alternating extremes, and random arrays.
• Assert heap order after construction and every extraction in debug/property tests.
• Verify sortedness and multiset preservation against the library sort.

• Specify mutation, order, comparator, null policy, and instability.
• For top-k rather than a full order, a bounded heap can reduce work to O(n log k).
• Sort indices/references when swapping large records would be expensive.
• Prefer tuned library sorting unless worst-case/in-place constraints justify custom code.

⚡ Complexity Analysis

Time Complexity

•
O(n log n) - All Cases
Consistent performance regardless of input.

Space Complexity

✓
O(1)
In-place sorting.

Tip: Instability

Heap Sort is unstable. It might change the relative order of equal elements. If stability is required (e.g., sorting by multiple criteria), Merge Sort or TimSort is preferred.

Heap Sort

What actually happens

How to choose heap sort

Quantitative check

Heap Sort Visualizer

How it works

Build Max Heap

Swap Root with End

Heapify

Repeat

🔎 Invariants, Trace, and Java Notes

Heap Invariant

Trace: [4, 10, 3, 5]

When to Use

💻 Implementation

Python

Java

Why Floyd heap construction is Θ(n), not Θ(n log n)

Exercises

Primary sources

Exercises

Primary sources

Exercises

Primary sources

Two-region invariant and proof

Before each extraction

Preservation

Performance profile and adversarial cases

Test and API checklist

⚡ Complexity Analysis

Time Complexity

Space Complexity

Tip: Instability

✅ Pros & ❌ Cons

✅ Advantages

❌ Disadvantages