Heap Extract Min or Max Bubble Down in DSA Java - 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 and performing bubble down?

DSA Java

int[] heap = {1, 3, 6, 5, 9, 8};
// Extract min (root) and bubble down
int last = heap[heap.length - 1];
heap[0] = last;
int size = heap.length - 1;
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) {
        int temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;
        i = smallest;
    } else {
        break;
    }
}
// Print heap array after extraction and bubble down
System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(heap, size)));

A [3, 5, 6, 8, 9]

B [5, 3, 6, 8, 9]

C [6, 3, 5, 8, 9]

D [3, 6, 5, 8, 9]

💡 Hint

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

After removing the root (1), we replace it with the last element (8). Then bubble down swaps 8 with the smaller child 3, then 8 with 5, resulting in [3, 5, 6, 8, 9].

❓ 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 and performing bubble down?

DSA Java

int[] heap = {20, 18, 15, 13, 10, 8, 9};
// Extract max (root) and bubble down
int last = heap[heap.length - 1];
heap[0] = last;
int size = heap.length - 1;
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) {
        int temp = heap[i];
        heap[i] = heap[largest];
        heap[largest] = temp;
        i = largest;
    } else {
        break;
    }
}
// Print heap array after extraction and bubble down
System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(heap, size)));

A [15, 18, 13, 9, 10, 8]

B [18, 13, 9, 15, 10, 8]

C [18, 15, 13, 9, 10, 8]

D [18, 13, 15, 9, 10, 8]

💡 Hint

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

After removing the root (20), we replace it with the last element (9). Then bubble down swaps 9 with the larger child 18, then 9 with 13, resulting in [18, 13, 15, 9, 10, 8].

🔧 Debug

advanced

Identify the Bug in Bubble Down Implementation

Which option contains a bug that causes an infinite loop during bubble down in a min-heap extract-min operation?

DSA Java

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) {
        int temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;
        i = smallest;
    } else {
        break;
    }
}

A The loop updates i to smallest after swapping, so no infinite loop.

B The loop swaps with the larger child instead of smaller, causing infinite loop.

C The loop forgets to update i after swapping, causing infinite loop.

D The loop uses 'break' incorrectly, causing infinite loop.

💡 Hint

Check if the index i changes after swapping.

If i is not updated to smallest after swapping, the loop keeps swapping the same elements endlessly, causing infinite loop.

🧠 Conceptual

advanced

Why Bubble Down is Necessary After Extracting Root in Heap?

Why do we perform bubble down after removing the root element in a heap?

A To sort the entire heap array in ascending order.

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

C To remove duplicate elements from the heap.

D To increase the size of the heap by adding new elements.

💡 Hint

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

After removing the root, the last element is placed at root. Bubble down moves it down to restore heap order.

❓ Predict Output

expert

Final Heap State After Multiple Extract-Min Operations

Given the min-heap array, what is the heap state after extracting min twice with bubble down each time?

DSA Java

int[] heap = {2, 4, 3, 7, 6, 5};
int size = heap.length;
for (int count = 0; count < 2; count++) {
    int last = heap[size - 1];
    heap[0] = last;
    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) {
            int temp = heap[i];
            heap[i] = heap[smallest];
            heap[smallest] = temp;
            i = smallest;
        } else {
            break;
        }
    }
}
System.out.println(java.util.Arrays.toString(java.util.Arrays.copyOf(heap, size)));

A [4, 6, 5, 7]

B [4, 7, 5, 6]

C [3, 7, 5, 6]

D [3, 6, 5, 7]

💡 Hint

Perform extract-min twice and bubble down each time carefully.

First extract-min removes 2, replaces root with 5, bubble down results in [3,4,5,7,6]. Second extract-min removes 3, replaces root with 6, bubble down results in [4,6,5,7].

Practice

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

easy

A. To remove all leaf nodes from 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 insert a new element at the bottom of the heap

Solution

1. Step 1: Understand the extract operation

   When we remove the min or max element (usually the root), the heap may lose its order property.

2. Step 2: Purpose of bubble down

   Bubble down moves the new root element down the tree to restore the heap property by swapping it with the smaller (min-heap) or larger (max-heap) child.

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 order after extraction [OK]

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

Common Mistakes:

• Thinking bubble down inserts new elements
• Assuming bubble down removes leaf nodes
• Believing bubble down only swaps root and last element

2. Which of the following Java method signatures correctly represents a bubble down operation for a min-heap stored in an array?

easy

A. void bubbleDown(int[] heap, int index, int size)

B. int bubbleDown(int[] heap, int size)

C. void bubbleDown(int index, int[] heap)

D. boolean bubbleDown(int[] heap, int index)

Solution

1. Step 1: Identify parameters needed for bubble down

   We need the heap array, the current index to bubble down from, and the size of the heap to avoid out-of-bounds.

2. Step 2: Match method signature

   void bubbleDown(int[] heap, int index, int size) has all parameters in correct order and returns void as bubble down modifies the heap in place.

3. Final Answer:

   void bubbleDown(int[] heap, int index, int size) -> Option A

4. Quick Check:

   Correct parameters and void return for bubble down [OK]

Hint: Bubble down needs array, index, and size parameters [OK]

Common Mistakes:

• Missing size parameter causing index errors
• Wrong return type expecting a value
• Incorrect parameter order

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

medium

A. [3, 5, 7, 10]

B. [5, 7, 3, 10]

C. [3, 7, 5, 10]

D. [5, 3, 7, 10]

Solution

1. Step 1: Remove min and replace root

   Remove 2 (min), replace root with last element 7: [7, 5, 3, 10]

2. Step 2: Bubble down from root

   Compare 7 with children 5 and 3; smallest is 3. Swap 7 and 3: [3, 5, 7, 10]. Now 7 has children 10 only, 7 < 10, so stop.

3. Final Answer:

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

4. Quick Check:

   Bubble down restores min-heap order [OK]

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

Common Mistakes:

• Not replacing root with last element before bubble down
• Swapping with wrong child (larger instead of smaller)
• Stopping bubble down too early

4. Consider this bubble down code snippet for a max-heap. Identify the bug:

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

medium

A. The comparison operators should be < instead of > for max-heap

B. The left and right child indices calculation is incorrect

C. The recursive call should be bubbleDown(heap, index, size) instead of bubbleDown(heap, largest, size)

D. There is no bug; the code correctly performs bubble down

Solution

1. Step 1: Check child index calculations

   Left = 2*index+1 and right = 2*index+2 are correct for binary heap stored in array.

2. Step 2: Verify comparisons and recursion

   Comparisons use > for max-heap to find largest child. Recursive call uses largest index to continue bubbling down correctly.

3. Final Answer:

   There is no bug; the code correctly performs bubble down -> Option D

4. Quick Check:

   Child indices and recursion are correct [OK]

Hint: Check indices and recursion carefully; they are often correct [OK]

Common Mistakes:

• Confusing child index formulas
• Wrong comparison operators for max-heap
• Incorrect recursive call index

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

hard

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

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

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

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

Solution

1. Step 1: Extract max and replace root

   Remove 20, replace root with last element 8: [8, 18, 15, 10, 12, 9]

2. Step 2: Bubble down from root

   Compare 8 with children 18 and 15; largest is 18. Swap 8 and 18: [18, 8, 15, 10, 12, 9]. Now bubble down at index 1.

3. Step 3: Continue bubble down

   At index 1, children are 10 and 12; largest is 12. Swap 8 and 12: [18, 12, 15, 10, 8, 9]. At index 4, children do not exist, stop.

4. Final Answer:

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

5. Quick Check:

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

Hint: Replace root with last, swap down with largest child repeatedly [OK]

Common Mistakes:

• Not continuing bubble down after first swap
• Swapping with smaller child by mistake
• Forgetting to update heap size after extraction