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

Heap Extract Min or Max Bubble Down

📖 Scenario: Imagine you are managing a priority queue for tasks where the highest priority task is always processed first. This priority queue is implemented using a heap data structure.When a task is completed, you need to remove the top priority task and then adjust the heap to maintain the correct order.

🎯 Goal: You will build the core part of a heap: the extract operation that removes the top element (minimum or maximum) and then bubbles down the last element to restore the heap property.This teaches how to maintain heap order after extraction.

📋 What You'll Learn

Create an integer array called heap with a fixed set of values representing a valid max-heap

Create an integer variable called heapSize to track the current number of elements in the heap

Write a method called BubbleDown that takes an integer index and restores the max-heap property by swapping elements downwards

Write code to extract the max element from the heap by replacing the root with the last element, reducing heapSize, and calling BubbleDown

Print the heap array elements up to heapSize after extraction to show the updated heap

💡 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 max-heap array

Create an integer array called heap with these exact values: 100, 50, 30, 20, 40, 10, 5. Also create an integer variable called heapSize and set it to 7.

DSA C#

# Create the heap array and heapSize variable
# Your code here

Hint

The heap array holds the elements in max-heap order. The heapSize tracks how many elements are currently in the heap.

2

Add the BubbleDown method

Add a method called BubbleDown that takes an integer parameter index. Inside it, use a while loop to compare the element at index with its children and swap with the larger child if needed. Update index to the child's index after swapping. Stop when no swaps are needed or children are out of range.

DSA C#

int[] heap = {100, 50, 30, 20, 40, 10, 5};
int heapSize = 7;

// Add BubbleDown method below
# Your code here

Hint

Remember the left child index is 2 * index + 1 and right child is 2 * index + 2. Swap with the largest child if it is bigger than the current element.

3

Extract the max element and bubble down

Write code to extract the max element from the heap by replacing heap[0] with heap[heapSize - 1], then decrement heapSize by 1, and finally call BubbleDown(0) to restore the heap property.

DSA C#

int[] heap = {100, 50, 30, 20, 40, 10, 5};
int heapSize = 7;

void BubbleDown(int index)
{
    while (true)
    {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;

        if (left  heap[largest])
            largest = left;
        if (right  heap[largest])
            largest = right;

        if (largest == index)
            break;

        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;

        index = largest;
    }
}

// Extract max element and bubble down
# Your code here

Hint

Replace the root with the last element, reduce the heap size, then call BubbleDown starting at index 0.

4

Print the heap after extraction

Write a for loop to print all elements in heap from index 0 to heapSize - 1 separated by spaces on one line.

DSA C#

int[] heap = {100, 50, 30, 20, 40, 10, 5};
int heapSize = 7;

void BubbleDown(int index)
{
    while (true)
    {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;

        if (left  heap[largest])
            largest = left;
        if (right  heap[largest])
            largest = right;

        if (largest == index)
            break;

        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;

        index = largest;
    }
}

heap[0] = heap[heapSize - 1];
heapSize--;
BubbleDown(0);

// Print the heap elements after extraction
# Your code here

Hint

Loop from 0 to heapSize - 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 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