Heap Sort Algorithm

# CHAPTER 15

Heap Sort Algorithm #

1. Introduction #

• Bubble Sort is easy to code but takes a horrific $O(N^2)$ Time.

• Merge Sort is lightning fast at $O(N \log N)$ Time, but it requires allocating massive backup arrays, bloating Space Complexity to $O(N)$.

2. Learning Objectives #

• Understand the Two-Phase architecture of Heap Sort.

• Execute the $O(N)$ "Build-Heap" phase to restructure chaotic arrays.

• Execute the $O(N \log N)$ "Extraction" phase to finalize the sorting.

• Prove the $O(1)$ Space Complexity that makes Heap Sort superior to Merge Sort for embedded systems.

3. Phase 1: Build-Heap (Structuring the Chaos) #

The Strategy: We run the Heapify Down algorithm (from Chapter 14) on the internal nodes. *Shortcut:* We do NOT need to Heapify the Leaf nodes! (A leaf node has no children, so it is already a perfectly valid 1-node Heap). The leaves occupy exactly the back half of the array. We start at the last non-leaf parent (N/2 - 1) and work backward to Index 0.

Trace [4, 10, 3, 5, 1]:

1. 1. Last non-leaf node is at index 1 (Value 10).

1. 2. Heapify 10: Compare with children 5 and 1. It is already $>$ both. OK.

1. 3. Move backwards to index 0 (Value 4).

1. 4. Heapify 4: Compare with children 10 and 3. Largest is 10. Swap 4 and 10.

1. 5. Array becomes [10, 4, 3, 5, 1].

1. 6. Heapify 4 again (it moved to index 1): Compare with children 5, 1. Swap 4 and 5.

1. 7. Array becomes [10, 5, 3, 4, 1].

4. Phase 2: Extraction (The Sorting Engine) #

The Strategy:

1. 1. Swap Root to Back: Swap Index 0 (10) with the absolute last element in the array (1). Array becomes [1, 5, 3, 4, 10].

1. 2. Lock the Back: The number 10 is now in its final, perfectly sorted position at the end of the array! We mathematically "lock" that array slot and pretend the array is now 1 element smaller.

1. 3. Heapify Root: The new Root (1) is a weak number. Run Heapify Down on Index 0 to bubble it down and push the *next* largest number up to the Root.

1. 4. Repeat: Repeat this swapping and locking until the array size shrinks to 1.

Trace Phase 2:

1. 1. Swap 10 and 1. Array: [1, 5, 3, 4, | 10]. (Locked 10).

1. 2. Heapify 1. It swaps with 5. Array: [5, 1, 3, 4, | 10].

1. 3. Heapify 1 again. It swaps with 4. Array: [5, 4, 3, 1, | 10]. (Heap restored).

1. 4. Swap Root 5 to the back. Array: [1, 4, 3, | 5, 10]. (Locked 5).

1. 5. Heapify 1. Swaps with 4. Array: [4, 1, 3, | 5, 10].

1. 6. Swap Root 4 to back. Array: [3, 1, | 4, 5, 10].

1. 7. Swap Root 3 to back. Array: [1, | 3, 4, 5, 10].

5. Python Code Implementation #

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i] # Swap
        heapify(arr, n, largest) # Recurse

def heapSort(arr):
    n = len(arr)

    # Phase 1: Build Max-Heap (start at last non-leaf)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Phase 2: Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] # Swap Root to back
        heapify(arr, i, 0) # Heapify the reduced array (size i)

6. Complexity Analysis #

• Time Complexity (Build Heap): $O(N)$. (A mathematical optimization proves building a heap bottom-up takes linear time, not $N \log N$).

• Time Complexity (Extraction): $O(N \log N)$. (We extract $N$ elements, and each Heapify takes $\log N$ time).

• Total Time Complexity: $O(N \log N)$ Guaranteed Worst-Case.

• Space Complexity: $O(1)$ Constant Space. The algorithm mutates the original array in-place, making it vastly superior to Merge Sort for low-RAM systems!

7. Common Mistakes #

• Using a Min-Heap for Ascending Order: To sort an array in ascending order (1, 2, 3), you MUST use a Max-Heap. Why? Because you extract the massive Root and throw it to the *back* of the array. If you use a Min-Heap, you put the tiny numbers at the back, resulting in a descending reverse-sorted array!

8. Exercises #

1. 1. Execute Phase 1 (Build Max-Heap) manually on the array [2, 8, 5, 3, 9, 1]. Show the final state of the array before Phase 2 begins.

1. 2. In Phase 1, why is it mathematically redundant to call the Heapify function on indices greater than (N/2 - 1)?

9. MCQs with Answers #

11. Interview Preparation #

• *Algorithm Selection:* "You are programming the guidance computer for an interplanetary satellite. Memory RAM is extremely limited, and missing a processing deadline will crash the ship. Do you use QuickSort, Merge Sort, or Heap Sort?" *(Answer: Heap Sort! Merge Sort wastes too much RAM ($O(N)$ Space). QuickSort risks a catastrophic $O(N^2)$ Worst-Case time delay. Only Heap Sort guarantees blazing $O(N \log N)$ speed combined with zero RAM overhead ($O(1)$ Space). It is the ultimate bulletproof embedded algorithm!)*

12. Summary #

13. Next Chapter Recommendation #