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 = {1, 3, 6, 5, 9, 8};
// Extract min operation removes 1 and bubbles down
// Resulting heap array after bubble down?

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

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

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

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

💡 Hint

Remember the bubble down swaps the root with the smaller child until heap property is restored.

After removing 1, the last element 8 moves to root. Bubble down swaps 8 with smaller child 3, then 8 with 5. Final heap is [3, 5, 6, 8, 9].

❓ Predict Output

intermediate

Output of Extract-Max on a Max-Heap

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

DSA C#

int[] heap = {20, 18, 15, 13, 10, 12};
// Extract max removes 20 and bubbles down
// Resulting heap array after bubble down?

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

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

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

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

💡 Hint

Bubble down swaps root with the larger child until heap property is restored.

After removing 20, last element 12 moves to root. Bubble down swaps 12 with larger child 18, then 12 with 13. Final heap is [18, 13, 15, 12, 10].

🔧 Debug

advanced

Identify the Bug in Bubble Down Implementation

Which option contains a bug that causes incorrect bubble down behavior in a min-heap extract operation?

DSA C#

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

    if (left < size && heap[left] < heap[smallest])
        smallest = left;
    if (right < size && heap[right] < heap[smallest])
        smallest = right;

    if (smallest != index) {
        int temp = heap[index];
        heap[index] = heap[smallest];
        heap[smallest] = temp;
        BubbleDown(heap, smallest, size);
    }
}

A The recursive call uses 'index' instead of 'smallest', causing infinite recursion.

B The function correctly implements bubble down with no bugs.

C The swap is done before checking if smallest != index, causing unnecessary swaps.

D The function does not check if left and right children exist before comparing values.

💡 Hint

Check the recursive call parameter carefully.

Recursive call must be BubbleDown(heap, smallest, size) to continue bubbling down at the swapped child. Using 'index' causes infinite recursion.

🧠 Conceptual

advanced

Understanding Bubble Down Steps in Extract-Min

In a min-heap, after extracting the minimum element, which sequence of steps correctly describes the bubble down process?

A 1, 3, 2, 4

B 1, 2, 3, 4

C 2, 1, 3, 4

D 3, 2, 1, 4

💡 Hint

Think about what happens immediately after removing the root.

First, the root is replaced by the last element (1). Then comparisons and swaps happen repeatedly to restore heap order.

❓ Predict Output

expert

Final Heap After Multiple Extract-Min Operations

Given the min-heap array [2, 4, 3, 8, 10, 15, 20], what is the heap array after extracting the minimum element twice?

DSA C#

int[] heap = {2, 4, 3, 8, 10, 15, 20};
// Extract min twice with bubble down each time
// What is the heap array after these two extractions?

A [4, 8, 10, 20, 15]

B [3, 8, 15, 20, 10]

C [3, 8, 10, 20, 15]

D [4, 8, 15, 20, 10]

💡 Hint

Perform extract-min once, then again, applying bubble down each time.

First extract removes 2, last element 20 moves to root, bubble down swaps 20 with 3, then 20 with 15. Heap after first extract: [3, 4, 15, 8, 10, 20]. Second extract removes 3, last element 20 moves to root, bubble down swaps 20 with 4, then 20 with 8. Final heap: [4, 8, 15, 20, 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 restore the 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 all elements smaller than the root

Solution

1. Step 1: Understand the extract min operation

   When we remove the minimum element (root) from a min-heap, the last element is moved to the root position.

2. Step 2: Apply bubble down to restore heap property

   The bubble down operation moves this new root element down the tree by swapping it with the smaller child until the heap property is restored.

3. Final Answer:

   To restore the 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 by pushing root down [OK]

Common Mistakes:

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

2. Which of the following C# code snippets correctly swaps the root element with its smaller child during bubble down in a min-heap?

easy

A. int temp = heap[i]; heap[i] = heap[child]; heap[child] = heap[i];

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

C. swap(heap[i], heap[child]);

D. int temp = heap[i]; heap[i] = heap[child]; heap[child] = temp;

Solution

1. Step 1: Identify correct swap syntax in C#

   int temp = heap[i]; heap[i] = heap[child]; heap[child] = temp; uses a temporary variable to swap two elements correctly, which is the standard way in C#.

2. Step 2: Check other options for correctness

   B: heap[i] = heap[child]; heap[child] = heap[i]; assigns values incorrectly causing data loss. C: swap(heap[i], heap[child]); is invalid syntax in C#. D: int temp = heap[i]; heap[i] = heap[child]; heap[child] = heap[i]; uses temp but assigns heap[child] the updated heap[i] value, causing no swap and data loss.

3. Final Answer:

   int temp = heap[i]; heap[i] = heap[child]; heap[child] = temp; -> Option D

4. Quick Check:

   Use temp variable to swap in C# [OK]

Hint: Use temp variable to swap array elements [OK]

Common Mistakes:

• Trying to swap without temp variable
• Using invalid syntax like swap() function
• Forgetting to use temp in the final assignment

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

medium

A. [5, 7, 3, 10]

B. [3, 5, 7, 10]

C. [3, 7, 5, 10]

D. [5, 3, 7, 10]

Solution

1. Step 1: Extract min and replace root

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

2. Step 2: Bubble down 7 to restore 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, which is larger, so stop.

3. Final Answer:

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

4. Quick Check:

   Extract min + bubble down = [3,5,7,10] [OK]

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

Common Mistakes:

• Not moving last element to root 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 in C#:

void BubbleDown(int[] heap, int i, int size) {
  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;
    BubbleDown(heap, largest, size);
  }
}

What is the bug if the heap array is empty (size = 0) and we call BubbleDown(heap, 0, 0)?

medium

A. Infinite recursion occurs

B. Heap property is violated after call

C. No bug; function exits immediately

D. Index out of range error when accessing heap[left]

Solution

1. Step 1: Analyze execution with size=0

   i=0, left=1, right=2. if(1 < 0 && ...) false due to short-circuit, no access to heap[1] or heap[0]. Similarly for right.

2. Step 2: Confirm safe exit

   largest=0 == i, no swap or recursion. Function exits immediately without any array access.

3. Final Answer:

   No bug; function exits immediately -> Option C

4. Quick Check:

   Short-circuit prevents access on empty heap [OK]

Hint: Rely on short-circuit evaluation for bounds safety [OK]

Common Mistakes:

• Misunderstanding C# short-circuit evaluation
• Assuming heap[largest] is always accessed
• Overlooking that no array access occurs

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

hard

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

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

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

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

Solution

1. Step 1: Extract 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

   Children: 30 (idx1), 40 (idx2). Largest is 40. Swap 35 and 40: [40, 30, 35, 10, 20]. Now at idx2 (35), children idx5 and 6 >= size 5, no children. Stop.

3. Final Answer:

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

4. Quick Check:

   Extract max + bubble down = [40,30,35,10,20] [OK]

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

Common Mistakes:

• Swapping with smaller child in max-heap
• Incorrectly identifying children during bubble down
• Not moving last element to root before bubble down