Heap Extract Min or Max Bubble Down in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Extract-Min on a Min-Heap

What is the state of the min-heap array after extracting the minimum element once?

DSA C

int heap[] = {2, 5, 3, 10, 7, 6};
int size = 6;

// Extract min operation
heap[0] = heap[size - 1];
size--;

// Bubble down
int i = 0;
while (true) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int smallest = i;
    if (left < size && heap[left] < heap[smallest]) smallest = left;
    if (right < size && heap[right] < heap[smallest]) smallest = right;
    if (smallest == i) break;
    int temp = heap[i];
    heap[i] = heap[smallest];
    heap[smallest] = temp;
    i = smallest;
}

// Print heap
for (int j = 0; j < size; j++) {
    printf("%d ", heap[j]);
}

A [6, 5, 3, 10, 7]

B [3, 5, 7, 10, 6]

C [5, 7, 3, 10, 6]

D [3, 5, 6, 10, 7]

💡 Hint

Remember to replace the root with the last element and then bubble down by swapping with the smaller child.

After removing the root (2), we replace it with the last element (6). Then we bubble down: 6 swaps with 3 (smaller child), resulting in [3, 5, 6, 10, 7].

❓ Predict Output

intermediate

Output of Extract-Max on a Max-Heap

What is the state of the max-heap array after extracting the maximum element once?

DSA C

int heap[] = {20, 15, 18, 10, 12, 17};
int size = 6;

// Extract max operation
heap[0] = heap[size - 1];
size--;

// Bubble down
int i = 0;
while (true) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < size && heap[left] > heap[largest]) largest = left;
    if (right < size && heap[right] > heap[largest]) largest = right;
    if (largest == i) break;
    int temp = heap[i];
    heap[i] = heap[largest];
    heap[largest] = temp;
    i = largest;
}

// Print heap
for (int j = 0; j < size; j++) {
    printf("%d ", heap[j]);
}

A [17, 15, 18, 10, 12]

B [18, 15, 12, 10, 17]

C [18, 15, 17, 10, 12]

D [15, 12, 17, 10, 18]

💡 Hint

Replace the root with the last element and bubble down by swapping with the larger child.

After removing the root (20), replace it with last element (17). Bubble down swaps 17 with 18 (larger child), resulting in [18, 15, 17, 10, 12].

🔧 Debug

advanced

Identify the Bug in Bubble Down for Min-Heap

What error will this bubble down code cause when extracting min from a min-heap?

DSA C

int heap[] = {1, 3, 6, 5, 9, 8};
int size = 6;

heap[0] = heap[size - 1];
size--;

int i = 0;
while (i < size) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int smallest = i;
    if (left < size && heap[left] < heap[smallest]) smallest = left;
    if (right < size && heap[right] < heap[smallest]) smallest = right;
    if (smallest == i) break;
    int temp = heap[i];
    heap[i] = heap[smallest];
    heap[smallest] = temp;
    i = smallest;
}

A Array index out of bounds error

B Segmentation fault

C No error, works correctly

D Infinite loop

💡 Hint

Check the conditions for left and right child indices compared to size.

The conditions use 'left <= size' and 'right <= size', but valid indices are less than size. This causes out-of-bounds access.

🧠 Conceptual

advanced

Why Bubble Down is Needed After Extracting Root in Heap?

Why do we need to perform bubble down after replacing the root with the last element in a heap?

A Because bubble down sorts the entire heap array

B Because the last element might violate the heap property at the root and needs to move down to restore order

C Because bubble down removes duplicate elements from the heap

D Because bubble down increases the heap size by adding new elements

💡 Hint

Think about what happens when the root is replaced by the last element.

Replacing the root with the last element may break the heap property at the root. Bubble down moves this element down to restore the heap order.

❓ Predict Output

expert

Final Heap State After Multiple Extract-Min Operations

Given the min-heap array [4, 7, 6, 10, 9, 8], what is the heap array after extracting the minimum element twice (two extract-min operations with bubble down each time)?

DSA C

int heap[] = {4, 7, 6, 10, 9, 8};
int size = 6;

// First extract-min
heap[0] = heap[size - 1];
size--;
int i = 0;
while (true) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int smallest = i;
    if (left < size && heap[left] < heap[smallest]) smallest = left;
    if (right < size && heap[right] < heap[smallest]) smallest = right;
    if (smallest == i) break;
    int temp = heap[i];
    heap[i] = heap[smallest];
    heap[smallest] = temp;
    i = smallest;
}

// Second extract-min
heap[0] = heap[size - 1];
size--;
i = 0;
while (true) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int smallest = i;
    if (left < size && heap[left] < heap[smallest]) smallest = left;
    if (right < size && heap[right] < heap[smallest]) smallest = right;
    if (smallest == i) break;
    int temp = heap[i];
    heap[i] = heap[smallest];
    heap[smallest] = temp;
    i = smallest;
}

// Print heap
for (int j = 0; j < size; j++) {
    printf("%d ", heap[j]);
}

A [7, 9, 8, 10]

B [6, 9, 8, 10]

C [6, 8, 9, 10]

D [7, 8, 9, 10]

💡 Hint

Perform extract-min twice carefully, updating size and bubbling down each time.

First extract-min removes 4, replaces root with 8, bubble down swaps 8 with 6, resulting in [6,7,8,10,9]. Second extract-min removes 6, replaces root with 9, bubble down swaps 9 with 7, resulting in [7,9,8,10].

Practice

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

easy

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

B. To restore the heap property by moving the root element down to its correct position

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

D. To remove all elements smaller than the root

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 smaller children.

3. Final Answer:

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

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
• Assuming bubble down only swaps root with last element
• Confusing bubble down with bubble up

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

easy

A. temp = heap[i]; heap[i] = heap[j]; heap[j] = temp;

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

C. heap[i], heap[j] = heap[j], heap[i];

D. heap[i] <-> heap[j];

Solution

1. Step 1: Recognize C swap syntax

   In C, swapping requires a temporary variable to hold one value during exchange.

2. Step 2: Verify temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses temp variable correctly

   temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses a temporary variable to swap values correctly, while others use invalid or non-C syntax.

3. Final Answer:

   temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; -> Option A

4. Quick Check:

   C swap needs temp variable [OK]

Hint: Use temp variable to swap in C [OK]

Common Mistakes:

• Using Python or pseudocode swap syntax in C
• Trying to swap without temp variable
• Using invalid operators like <->

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

medium

A. [4, 7, 5, 10, 6]

B. [5, 4, 6, 10, 7]

C. [6, 4, 5, 10, 7]

D. [4, 6, 5, 10, 7]

Solution

1. Step 1: Remove root and replace with last element

   Remove 2, move last element 6 to root: [6, 4, 5, 10, 7]

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

   Compare 6 with children 4 and 5; swap with smallest child 4: [4, 6, 5, 10, 7]. Next, 6's children are 10 and 7, both larger, so stop.

3. Final Answer:

   [4, 6, 5, 10, 7] -> Option D

4. Quick Check:

   Bubble down swaps with smaller child [OK]

Hint: Replace root with last, then bubble down [OK]

Common Mistakes:

• Not swapping with the smallest child
• Stopping bubble down too early
• Replacing root incorrectly

4. Consider this bubble down code snippet for a max-heap in C. What is the bug?

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

medium

A. No bug, code correctly bubbles down in max-heap

B. Left and right child indices calculation is wrong

C. Recursive call should be bubbleDown(heap, size, i) instead of largest

D. Swapping should happen only if heap[i] < heap[largest]

Solution

1. Step 1: Check child index calculations

   Left = 2*i+1 and right = 2*i+2 are correct for zero-based heap arrays.

2. Step 2: Verify bubble down logic

   Code finds largest among node and children, swaps if needed, then recurses on swapped child. This matches max-heap bubble down logic.

3. Final Answer:

   No bug, code correctly bubbles down in max-heap -> Option A

4. Quick Check:

   Correct child indices and recursion [OK]

Hint: Check child indices and recursion carefully [OK]

Common Mistakes:

• Confusing left/right child index formulas
• Wrong recursive call index
• Swapping condition misunderstanding

5. You have a max-heap represented by the array [20, 18, 15, 10, 12, 9, 8]. After extracting the maximum element and performing bubble down, what is the final heap array?

hard

A. [18, 12, 15, 10, 9, 8]

B. [18, 10, 15, 8, 12, 9]

C. [18, 12, 15, 10, 8, 9]

D. [18, 15, 12, 10, 9, 8]

Solution

1. Step 1: Remove root and replace with last element

   Remove 20, move last element 8 to root: [8, 18, 15, 10, 12, 9]

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

   Compare 8 with children 18 and 15; swap with largest child 18: [18, 8, 15, 10, 12, 9]. Next, 8's children are 10 and 12; swap with largest child 12: [18, 12, 15, 10, 8, 9]. Now 8's children are out of range, stop.

3. Final Answer:

   [18, 12, 15, 10, 8, 9] -> Option C

4. Quick Check:

   Bubble down swaps with largest child until heap property restored [OK]

Hint: Replace root with last, bubble down swapping largest child [OK]

Common Mistakes:

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