Heaps and Priority Heaps

# CHAPTER 22

Heaps and Priority Heaps #

1. Introduction #

2. Learning Objectives #

• Define the architectural laws of Min-Heaps and Max-Heaps.

• Understand how Complete Binary Trees allow Heaps to be secretly stored in flat Arrays.

• Execute the Heapify (Bubble-Up / Sink-Down) algorithms.

• Analyze the exact Time Complexity of extracting the Root node.

3. The Two Laws of the Heap #

#### Law 1: The Shape Property (Complete Binary Tree) A Heap must be a Complete Binary Tree. This means every single level of the tree must be 100% full before starting a new level. Furthermore, the bottom level must be filled explicitly from Left to Right, with absolutely no gaps.

#### Law 2: The Heap Property (Max or Min)

• Max-Heap: Every Parent node must be mathematically GREATER than or equal to both of its children. (The absolute largest number in the dataset sits on the Throne at the Root).

• Min-Heap: Every Parent node must be mathematically SMALLER than or equal to both of its children. (The absolute smallest number sits at the Root).

*Crucial Note: Unlike a BST, there is NO mathematical relationship between siblings! The left child can be larger than the right child. The only rule is Parent > Children.*

4. The Array Secret (O(1) Pointers) #

If a Parent Node is at array index i:

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

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

• Parent Index: (i - 1) / 2

Visualizing the Array Trick:

Tree:       [100]
           /     \
         [50]    [70]
        /   \
      [10]  [20]

Array: [100, 50, 70, 10, 20]

*Index 1 is 50. Its left child is (2 * 1) + 1 = 3. Index 3 is 10. The math is perfectly flawless and requires zero RAM overhead for pointers!*

5. Insertion (Bubbling Up) #

1. 1. Insert at the Bottom: Because it's a Complete Tree, 90 MUST be placed at the first available gap (the left child of 70). Array becomes: [100, 50, 70, 10, 20, 90].

1. 2. Heapify Up (Bubble Up): 90 is larger than its parent 70. This violates the Max-Heap law! We swap them. 90 bubbles up.

1. 3. Check again. 90 is smaller than the Root 100. The law is satisfied. The bubbling stops.

6. Deletion (Sinking Down) #

1. 1. Remove Root: 100 is extracted. The throne is empty.

1. 2. Move the Bottom up: Take the absolute last element in the array (70) and place it on the Root throne.

1. 3. Heapify Down (Sink Down): 70 looks at its children (50 and 90). 90 is larger! 70 swaps with 90, sinking down to restore the Max-Heap law.

7. Implementation Concept #

# Python Example: Max-Heap Sinking Algorithm (Heapify Down)
def heapify_down(arr, n, i):
    largest = i           # Assume Parent is largest
    left = 2 * i + 1      # Left child math
    right = 2 * i + 2     # Right child math

    # Is left child larger than Parent?
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Is right child larger than the current largest?
    if right < n and arr[right] > arr[largest]:
        largest = right

    # If the Parent is NOT the largest, SWAP and recurse!
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i] # Swap
        heapify_down(arr, n, largest) # Recursively sink down!

8. Complexity Analysis #

9. Real-World Applications #

1. 1. Priority Queues: As covered in Chapter 15, Heaps are the explicit engine driving OS Task Scheduling and Dijkstra's Shortest Path algorithm.

1. 2. Heap Sort: One of the most efficient sorting algorithms in existence. You dump an array of unsorted numbers into a Min-Heap (takes O(n log n)), and then you extract_root() over and over. The numbers pop out in perfect sorted order!

10. Common Mistakes #

• Confusing a Heap with a BST: A Heap is NOT sorted horizontally! If you do an In-Order traversal of a Heap, the numbers will print out in complete gibberish. A Heap only guarantees vertical sorting (Parent > Child). Do not use a Heap to search for a random number X (it will take O(n) time). Use it strictly to find the Maximum or Minimum.

11. Exercises #

1. 1. Trace the Array math: If an element sits at Array index 6, what are the exact Array indexes of its Parent, its Left Child, and its Right Child?

1. 2. Draw a Max-Heap containing 10, 20, 15, 30, 40. *(Hint: Insert them one by one and Bubble Up!)*

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Find the K-th largest element in an unsorted array of 1 million numbers." *(Answer: Do NOT sort the massive array! That takes O(N log N). Instead, create a Min-Heap of size K. Loop through the array, pushing numbers into the Heap. If the heap size exceeds K, pop the smallest element. At the end of the loop, the absolute root of your tiny Heap is the K-th largest number! Time Complexity: O(N log K)!).*

Common Pitfalls:

• In whiteboard interviews, accidentally drawing a Heap that is not a Complete Binary Tree. If you draw a right child without first drawing a left child, you have fundamentally broken the underlying Array mathematics, and the interviewer will fail the diagram.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #