Skip to main content
Binary Trees & Graphs
CHAPTER 14 Beginner

Min Heap and Max Heap

Updated: May 17, 2026
10 min read

# CHAPTER 14

Min Heap and Max Heap

1. Introduction

In Chapter 13, we defined the strict mathematical layout of a Binary Heap. The structure must be a Complete Tree (packed left-to-right), and the nodes must obey Vertical Dominance (Parents $>$ Children for Max-Heap). But what happens when you insert a brand new item into the array? Or when you execute the primary feature of a Heap: deleting the Root node to extract the highest priority item? The entire mathematical architecture shatters. We must deploy rapid algorithmic surgical strikes—known as Heapify—to manually "bubble" integers up and down the array until the vertical geometry is flawlessly restored.

2. Learning Objectives

By the end of this chapter, you will be able to:
  • Trace the algorithmic trajectory of a Heap Insertion (Bubble Up).
  • Trace the algorithmic trajectory of a Heap Deletion (Bubble Down / Heapify).
  • Execute array-based index swapping to restore Vertical Dominance.
  • Translate Heap mechanics into executable programmatic code.

3. Heap Insertion (Bubble Up / Sift Up)

When inserting a new element, we must satisfy Rule 1 (Complete Tree Packing) before we satisfy Rule 2 (Vertical Dominance).

The Algorithm (Max-Heap):

  1. 1. Append: Push the new element to the absolute end of the Array. (This guarantees it is placed in the perfect left-to-right bottom position of the Complete Tree).
  1. 2. Compare: Look at its mathematical Parent using (i - 1) / 2.
  1. 3. Bubble Up: If the new Child is strictly Greater Than ($>$) the Parent, they violate the rules. Physically swap their array indices.
  1. 4. Recurse: Repeat the comparison up the tree until the element becomes smaller than its Parent, or it hits the absolute Root (Index 0).

Visual Trace (Insert 90 into Max-Heap): Array: [100, 50, 80, 10, 30]

  1. 1. Append 90: [100, 50, 80, 10, 30, 90]. Node 90 is at index 5.
  1. 2. Parent of 90 is (5-1)/2 = Index 2 (80).
  1. 3. Is 90 > 80? Yes! Swap them.
  1. 4. Array becomes [100, 50, 90, 10, 30, 80]. 90 is now at index 2.
  1. 5. Parent of 90 is (2-1)/2 = Index 0 (100).
  1. 6. Is 90 > 100? No. Stop. The Heap is healed!

4. Heap Deletion (Extract Max / Heapify Down)

A Priority Queue ONLY deletes the absolute maximum (or minimum) priority element. You exclusively delete the Root Node (Index 0). If you delete Index 0, the entire top of the pyramid is missing. How do we fix it?

The Algorithm (Max-Heap):

  1. 1. Swap: Grab the absolute *last* element in the array and overwrite the Root (Index 0) with it.
  1. 2. Delete: Pop the last element from the array entirely. (The tree is now perfectly Complete, but the Root is likely a tiny number, violating Dominance!).
  1. 3. Heapify Down (Sift Down): Compare the new Root to its Left and Right children.
  1. 4. Swap: Find the *largest* of the two children. If the child is Greater Than the parent, swap them.
  1. 5. Recurse: Plunge downward, swapping until the node is larger than both children or hits the bottom row.

Visual Trace (Extract Max 100): Array: [100, 50, 90, 10, 30, 80]

  1. 1. Overwrite Root with last item (80). Array: [80, 50, 90, 10, 30].
  1. 2. Compare Root 80 to children 50 and 90.
  1. 3. The largest child is 90. Is 90 > 80? Yes! Swap them.
  1. 4. Array becomes [90, 50, 80, 10, 30].
  1. 5. The Heap is healed! 90 is the new global maximum!

5. Code Execution: Heapify Down

This algorithm is the core engine of all Priority Queues.

Python:

python
1234567891011121314151617 
def heapify_down(arr, n, i):
    largest = i  # Initialize parent as largest
    left = 2 * i + 1
    right = 2 * i + 2
    
    # Check if left child exists and is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left
        
    # Check if right child exists and is greater than current largest
    if right < n and arr[right] > arr[largest]:
        largest = right
        
    # If the parent is no longer the largest, SWAP and Recurse!
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i] # Swap variables
        heapify_down(arr, n, largest) # Plunge downward!

6. Min-Heap vs. Max-Heap Logic

The mechanical algorithms are identical. The *only* change is flipping the comparison operators (> to <).
  • Max-Heap Bubble Up: Swap if Child > Parent.
  • Min-Heap Bubble Up: Swap if Child < Parent.
  • Max-Heap Heapify Down: Swap with the *Largest* child if Parent < Child.
  • Min-Heap Heapify Down: Swap with the *Smallest* child if Parent > Child.

7. Complexity Analysis

  • Time Complexity (Insertion - Bubble Up): $O(\log N)$. The element traces a single path from bottom to top.
  • Time Complexity (Extraction - Heapify Down): $O(\log N)$. The element traces a single path from top to bottom.
  • Get Max/Min: $O(1)$. It is instantly available at Index 0.

8. Common Mistakes

  • Swapping with the wrong child during Deletion: When a parent bubbles down in a Max-Heap, you MUST compare both the Left and Right children, find the *Absolute Largest* of the two, and swap with that one! If you blindly swap with the Left child, the Right child might end up larger than the new Parent, permanently corrupting the matrix.

9. Exercises

  1. 1. Perform an "Extract Min" deletion on the following Min-Heap array: [5, 10, 15, 20, 30, 40]. Write out the array state after the final Heapify Down rotation completes.
  1. 2. If you insert the number 99 into a Max-Heap of size $31$, exactly how many array swaps will occur in the absolute worst-case mathematical scenario?

10. MCQs with Answers

Question 1

When an insertion algorithm injects a new variable into a localized Heap matrix, where does it geometrically anchor the new data point before initiating the sorting phase?

Question 2

What physical algorithmic operation defines the "Bubble Up" (Sift Up) mechanical repair cycle?

Question 3

When a Priority Queue executes its primary extraction command, which localized node is explicitly deleted from the architecture?

Question 4

To execute a mathematically safe Root Extraction without shattering the underlying array density rules, what specific replacement variable is forcefully written into the vacant Index 0 slot?

Question 5

Because injecting a tiny terminal leaf integer directly into the sovereign Root slot violates Vertical Dominance, the "Heapify Down" repair engine initiates. What does it do?

Question 6

During a Max-Heap "Heapify Down" cycle, why is it functionally critical that the Parent swaps exclusively with the *Absolute Largest* of its two localized children?

Question 7

What defines the foundational algorithmic Time Complexity for executing a singular "Bubble Up" or "Heapify Down" rotational cycle?

Question 8

If an engineer converts a Max-Heap array into a Min-Heap, what explicit mathematical modification must occur within the algorithmic execution script?

Question 9

If a Heap array possesses $31$ densely packed nodes, what is the absolute worst-case integer sum of localized index swaps required to fully execute a Bubble Up insertion?

Q10. True or False: You can execute a standard Binary Search traversal upon a valid Max-Heap to quickly locate the median numerical variable. a) True. Heaps and BSTs share structural search logic. b) False. A Heap fundamentally sacrifices lateral sorting geometry to maximize vertical extraction speeds. Sibling nodes possess absolute zero relational constraints, rendering highly structured logarithmic tracking mechanisms entirely useless. Finding a median requires $O(N)$ linear scans. Answer: b) False. A Heap fundamentally sacrifices lateral sorting geometry to maximize vertical...

11. Interview Preparation

Top Interview Questions:
  • *Algorithmic Hardware Deployment:* "You are designing the load balancer for a high-frequency trading platform. Orders must be executed purely by their bid price. How do you structure the incoming array buffer?" *(Answer: Do not sort the array! Deploy a Max-Heap Priority Queue. Incoming bids trigger a $O(\log n)$ Bubble Up. The execution engine runs $O(1)$ Extract-Max, triggering a $O(\log n)$ Heapify Down. The system continuously processes absolute maximums flawlessly without ever wasting CPU cycles executing full $O(N \log N)$ array sorts!)*

12. Summary

Heaps are raw mechanical engines of efficiency. The "Bubble Up" insertion appends to the tail and floats data to the top. The "Heapify Down" extraction rips the head off, patches it with the tail, and sinks the weak data back down the hierarchy. By mastering these two logarithmic $O(\log N)$ array-swapping algorithms, you possess the architecture to build ultra-fast real-time schedulers.

13. Next Chapter Recommendation

We know how to insert and delete from a Heap. What if we apply these algorithms to a random, unsorted array of numbers? Could we use the Heapify engine to mathematically sort an entire array in place, without using any extra memory? In Chapter 15: Heap Sort Algorithm, we unlock one of the most powerful and memory-efficient sorting architectures in computer science.

Finish this Chapter

Save your progress on your learning path and prepare for coding interview challenges.

Previous Chapter Heap Data Structures
Next Chapter Heap Sort Algorithm

Discussion

Join the discussion

Log in or create a free account to participate.

Sort: ·

Explore More

📖 Related Tutorials 4

❓ Related Quizzes 5

🧪 Related Labs 3