Heap Extract Min or Max Bubble Down in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the index of the left child in a heap array.

DSA C#

int leftChildIndex = 2 * parentIndex [1] 1;

Drag options to blanks, or click blank then click option'

A+

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using minus instead of plus.

Using multiplication or division instead of addition.

In a heap stored as an array, the left child of a node at index parentIndex is at 2 * parentIndex + 1.

2fill in blank

medium

Complete the code to swap two elements in the heap array.

DSA C#

int temp = heapArray[i];
heapArray[i] = heapArray[[1]];
heapArray[[1]] = temp;

Drag options to blanks, or click blank then click option'

Aparent

Bi

Cj

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index twice.

Swapping with an undefined variable.

To swap elements at indices i and j, use heapArray[j] in the swap.

3fill in blank

hard

Fix the error in the bubble down condition to continue while the child index is valid.

DSA C#

while (childIndex [1] heapSize) {
    // bubble down logic
}

Drag options to blanks, or click blank then click option'

A>

B<

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than or equal which causes out of bounds.

Using less than or equal which may cause off-by-one errors.

The loop should continue while childIndex is less than heapSize to stay within array bounds.

4fill in blank

hard

Fill both blanks to correctly find the smaller child index during bubble down.

DSA C#

if (rightChildIndex < heapSize && heapArray[rightChildIndex] [1] heapArray[leftChildIndex]) {
    smallerChildIndex = [2];
} else {
    smallerChildIndex = leftChildIndex;
}

Drag options to blanks, or click blank then click option'

A<

B>

CrightChildIndex

DleftChildIndex

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than instead of less than.

Assigning the wrong child index.

We compare right and left child values to find the smaller child. If right child is smaller, assign its index.

5fill in blank

hard

Fill all three blanks to complete the bubble down swap and update indices.

DSA C#

int temp = heapArray[[1]];
heapArray[[1]] = heapArray[[2]];
heapArray[[2]] = temp;

parentIndex = [3];

Drag options to blanks, or click blank then click option'

AparentIndex

BsmallerChildIndex

CchildIndex

DheapSize

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping wrong indices.

Not updating parentIndex correctly.

Swap values at parentIndex and smallerChildIndex, then update parentIndex to smallerChildIndex for next iteration.

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