Heap Sort Algorithm

# CHAPTER 17

Heap Sort Algorithm #

1. Introduction #

2. Learning Objectives #

• Define the Heap "Shape Property" and "Max-Heap Property".

• Execute mathematical index jumping (Parent, Left Child, Right Child).

• Understand the "Heapify" (Sink-Down) mutation logic.

• Trace the extraction phase of Heap Sort.

3. The Core Concept: The Array as a Tree #

Because it is a "Complete" tree (no gaps, filled perfectly left-to-right), we do not need physical node objects or left/right RAM pointers. We can map the tree directly onto a flat array using integer math!

If a Parent is at Index i:

• Left Child Index: (2 * i) + 1

• Right Child Index: (2 * i) + 2

4. Phase 1: Building the Max-Heap (Heapify) #

*Result of Phase 1:* The array physically transforms into [10, 5, 3, 4, 1]. The absolute massive maximum (10) is now sitting at Index 0!

5. Phase 2: Extraction and Sorting #

1. 1. Extract: We grab the Root (10) and swap it with the absolute LAST element in the array (1).

1. 2. Lock: The number 10 is now permanently locked into its finalized, sorted position at the far right!

1. 3. Sink Down: The Root is now 1. This violates the Max-Heap Law! We trigger the Heapify logic to violently sink 1 downward, which naturally forces the next-largest number (5) to bubble up to the Root throne.

1. 4. Repeat: Swap the new Root (5) to the end of the array, lock it, and Heapify again.

6. Implementation in Code #

// Java Example: Heap Sort
public class HeapSort {
    
    // The Execution Controller
    public void sort(int arr[]) {
        int n = arr.length;

        // PHASE 1: Build the initial Max-Heap
        // We start exactly at the lowest Parent node and work upward to the Root
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // PHASE 2: Extract the Root iteratively
        for (int i = n - 1; i > 0; i--) {
            // Swap the massive Root [0] to the end of the shrinking array [i]
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Trigger the Sink-Down logic to restore the damaged Root
            heapify(arr, i, 0); 
        }
    }

    // The Mathematical Sink-Down Engine
    void heapify(int arr[], int n, int i) {
        int largest = i; // Assume the Parent is the largest
        int left = 2 * i + 1; // Left child math
        int right = 2 * i + 2; // Right child math

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

        // If the right child is larger than the current largest
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // If the Parent was NOT the largest, a violation occurred!
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively sink the node further down the tree!
            heapify(arr, n, largest);
        }
    }
}

7. Complexity Analysis: Pure Perfection #

Why is it exactly $N \log N$? The array acts as a tree. The height of the tree is mathematically locked at log N. During the Extraction phase, we must extract N elements. Every extraction forces the new Root to sink down the height of the tree (log N). Multiply them together: $O(N \log N)$. Because we execute 100% of the swaps physically inside the original array utilizing index math, the Space Complexity is a perfect $O(1)$.

8. Stability Classification #

9. Real-World Applications #

• Introsort Core: As discussed in Chapter 16, modern C++ does not natively use pure Heap Sort because Quick Sort's hardware Cache Locality actually runs faster in the real world. However, if C++ detects that Quick Sort is failing into a catastrophic $O(N^2)$ spiral, it instantly aborts Quick Sort and switches the remaining data directly into Heap Sort, relying on Heap Sort's indestructible, guaranteed $O(N \log N)$ Worst-Case limit to rescue the server from crashing!

10. Common Mistakes #

• Using a Min-Heap: A common beginner mistake is using a Min-Heap (where the smallest number is at the Root) to sort an array in Ascending Order. This fails logically! If the smallest number is at the root, and you swap it to the end of the array, the smallest number gets locked into the highest index position! You MUST use a Max-Heap to sort Ascending, and a Min-Heap to sort Descending!

11. Exercises #

1. 1. Perform the index math: In an array acting as a Heap, what is the exact Left Child index, Right Child index, and Parent index of the element sitting at Index 4?

1. 2. Trace the first iteration of the Heapify logic manually on the array [1, 5, 3].

12. MCQs with Answers #

13. Interview Preparation #

• *System Design:* "An interviewer asks you to build a system that only needs to find the Top 5 highest scores in a massive dataset of 1 Billion users. Do you run Merge Sort to sort all 1 Billion users?" *(Answer: No! Running a full $O(N \log N)$ sort is massively wasteful. Build a Min-Heap of size exactly 5. Iterate linearly over the 1 Billion users, pushing them into the tiny Heap. If the heap grows to 6, pop the smallest. At the end, the 5 items remaining in the heap are the ultimate winners. Time Complexity: A blistering $O(N \log 5)$!).*

14. Summary #

15. Next Chapter Recommendation #