Heap Extract Min or Max Bubble Down in DSA C++ - Build from Scratch

Heap Extract Min or Max Bubble Down

📖 Scenario: You are managing a priority queue using a binary heap stored in an array. You want to remove the top element (minimum for min-heap or maximum for max-heap) and then restore the heap property by bubbling down the new root element.

🎯 Goal: Build a C++ program that extracts the root element from a heap array and restores the heap property by bubbling down the new root.

📋 What You'll Learn

Create an integer array called heap with the exact values: {10, 15, 20, 17, 25}

Create an integer variable called heap_size and set it to 5

Write a function called bubbleDown that takes heap, heap_size, and an integer index and restores the min-heap property by bubbling down the element at index

Write code to extract the minimum element (root) from the heap, replace it with the last element, reduce heap_size, and call bubbleDown on the root

Print the heap array elements separated by spaces after extraction and bubbling down

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and algorithms like Dijkstra's shortest path.

💼 Career

Understanding heap operations is important for software engineers working on performance-critical applications and system design.

1

Create the initial heap array

Create an integer array called heap with the exact values {10, 15, 20, 17, 25} and an integer variable called heap_size set to 5.

DSA C++

// Create the heap array and heap_size variable
// Your code here

Hint

Use int heap[] = {10, 15, 20, 17, 25}; and int heap_size = 5;.

2

Write the bubbleDown function

Write a function called bubbleDown that takes parameters int heap[], int heap_size, and int index. The function should restore the min-heap property by bubbling down the element at index until the heap property is satisfied.

DSA C++

int heap[] = {10, 15, 20, 17, 25};
int heap_size = 5;

// Write bubbleDown function below
// Your code here

Hint

Use recursion or a loop to swap the element at index with the smaller child until the min-heap property is restored.

3

Extract the minimum element and bubble down

Write code to extract the minimum element from the heap by replacing the root with the last element, decreasing heap_size by 1, and calling bubbleDown on index 0.

DSA C++

int heap[] = {10, 15, 20, 17, 25};
int heap_size = 5;

void bubbleDown(int heap[], int heap_size, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap_size && heap[left] < heap[smallest]) {
        smallest = left;
    }
    if (right < heap_size && heap[right] < heap[smallest]) {
        smallest = right;
    }
    if (smallest != index) {
        int temp = heap[index];
        heap[index] = heap[smallest];
        heap[smallest] = temp;
        bubbleDown(heap, heap_size, smallest);
    }
}

// Extract min and bubble down
// Your code here

Hint

Replace the root with the last element, reduce heap_size, then call bubbleDown on index 0.

4

Print the heap after extraction

Write a for loop to print the elements of heap from index 0 to heap_size - 1 separated by spaces.

DSA C++

int heap[] = {10, 15, 20, 17, 25};
int heap_size = 5;

void bubbleDown(int heap[], int heap_size, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap_size && heap[left] < heap[smallest]) {
        smallest = left;
    }
    if (right < heap_size && heap[right] < heap[smallest]) {
        smallest = right;
    }
    if (smallest != index) {
        int temp = heap[index];
        heap[index] = heap[smallest];
        heap[smallest] = temp;
        bubbleDown(heap, heap_size, smallest);
    }
}

heap[0] = heap[heap_size - 1];
heap_size--;
bubbleDown(heap, heap_size, 0);

// Print the heap elements
// Your code here

Hint

Use a for loop from 0 to heap_size - 1 and print each element followed by a space.

Practice

1. What is the main purpose of the bubble down operation in a min-heap after extracting the minimum element?

easy

A. To restore the min-heap property by moving the root element down to its correct position

B. To insert a new element at the bottom of the heap

C. To swap the last element with the root without any further changes

D. To remove the maximum element from the heap

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, the last element is moved to the root position.

2. Step 2: Apply bubble down to restore heap

   The bubble down operation moves this element down the tree to restore the min-heap property by swapping with the smaller child.

3. Final Answer:

   To restore the min-heap property by moving the root element down to its correct position -> Option A

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap after removing root [OK]

Common Mistakes:

• Thinking bubble down inserts new elements
• Confusing bubble down with bubble up
• Assuming bubble down removes max element

2. Which of the following is the correct C++ syntax to swap two elements heap[i] and heap[j] during bubble down?

easy

A. swap(heap[i], heap[j]){}

B. heap[i] = heap[j]; heap[j] = heap[i];

C. swap(heap[i], heap[j]) = true;

D. swap(heap[i], heap[j]);

Solution

1. Step 1: Recall C++ swap function usage

   The standard way to swap two variables in C++ is using swap(a, b); from <algorithm>.

2. Step 2: Check each option

   swap(heap[i], heap[j]); uses correct syntax. heap[i] = heap[j]; heap[j] = heap[i]; wrongly assigns values without temporary storage. Options C and D have invalid syntax.

3. Final Answer:

   swap(heap[i], heap[j]); -> Option D

4. Quick Check:

   Correct swap syntax = swap(heap[i], heap[j]); [OK]

Hint: Use standard swap function with two variables [OK]

Common Mistakes:

• Assigning without temporary variable causes errors
• Adding extra symbols after swap call
• Using braces {} after swap incorrectly

3. Given the min-heap array [2, 5, 3, 10, 7], after extracting the minimum element and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 7, 10]

B. [3, 7, 5, 10]

C. [5, 7, 3, 10]

D. [5, 3, 7, 10]

Solution

1. Step 1: Remove minimum and replace root

   Remove 2 (root). Move last element 7 to root: [7, 5, 3, 10]

2. Step 2: Bubble down 7 to restore min-heap

   Compare 7 with children 5 and 3. Smallest child is 3. Swap 7 and 3: [3, 5, 7, 10]. Now 7 has children 10 only, no swap needed.

3. Final Answer:

   [3, 5, 7, 10] -> Option A

4. Quick Check:

   Bubble down swaps root with smallest child [OK]

Hint: Replace root with last, then swap down with smaller child [OK]

Common Mistakes:

• Not swapping with smallest child first
• Forgetting to replace root with last element
• Swapping with larger child by mistake

4. Consider this bubble down code snippet for a max-heap extract operation:

void bubbleDown(vector<int>& heap, int i) {
  int left = 2*i + 1;
  int right = 2*i + 2;
  int largest = i;
  if (left < heap.size() && heap[left] > heap[largest])
    largest = left;
  if (right < heap.size() && heap[right] > heap[largest])
    largest = right;
  if (largest != i) {
    swap(heap[i], heap[largest]);
    bubbleDown(heap, largest);
  }
}

What is the bug if the heap size is 1 and bubbleDown(heap, 0) is called?

medium

A. Infinite recursion because largest never changes

B. No bug; function handles size 1 correctly

C. Accessing left child index 1 causes out-of-range error

D. Swap called even when largest equals i

Solution

1. Step 1: Check conditions for size 1 heap

   For size 1, left = 1 and right = 2, both >= heap.size(), so conditions fail and largest stays i.

2. Step 2: Confirm no recursion or swap

   Since largest == i, no swap or recursive call happens. Function returns safely.

3. Final Answer:

   No bug; function handles size 1 correctly -> Option B

4. Quick Check:

   Bounds checked before access prevents errors [OK]

Hint: Check index bounds before accessing children [OK]

Common Mistakes:

• Assuming out-of-range access without checking
• Thinking recursion always happens
• Swapping when largest equals current index

5. You have a max-heap represented as [50, 30, 40, 10, 20, 35]. After extracting the maximum element and performing bubble down, what is the final heap array?

hard

A. [40, 35, 30, 10, 20]

B. [40, 30, 20, 10, 35]

C. [40, 30, 35, 10, 20]

D. [35, 30, 40, 10, 20]

Solution

1. Step 1: Remove max and replace root

   Remove 50 (root). Move last element 35 to root: [35, 30, 40, 10, 20]

2. Step 2: Bubble down 35 to restore max-heap

   Compare 35 with children 30 and 40. Largest child is 40. Swap 35 and 40: [40, 30, 35, 10, 20]. Now 35 has children 10 and 20, both smaller, so stop.

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option C

4. Quick Check:

   Bubble down swaps with largest child in max-heap [OK]

Hint: Swap root with largest child until heap property restored [OK]

Common Mistakes:

• Swapping with smaller child instead of largest
• Not replacing root with last element before bubble down
• Stopping bubble down too early