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 at the top. You want to remove the top task and then adjust the queue so the next highest priority task moves to the top.

🎯 Goal: You will build a simple max-heap array and implement the extract max operation. This operation removes the largest element (root) and then uses bubble down to restore the heap property.

📋 What You'll Learn

Create an integer array called heap with these exact values: {40, 30, 20, 15, 10, 5}

Create an integer variable called heap_size and set it to 6

Write a function called bubble_down that takes heap, heap_size, and an integer index and restores the max-heap property by bubbling down the element at index

Write code to extract the max element from the heap by replacing the root with the last element, decreasing heap_size, and calling bubble_down on the root

Print the heap array elements separated by spaces after extraction and bubble down

💡 Why This Matters

🌍 Real World

Priority queues are used in operating systems for task scheduling, in network routers for managing packet priorities, and in many algorithms like Dijkstra's shortest path.

💼 Career

Understanding heap operations like extract max and bubble down is essential for software engineers working on performance-critical applications, data processing, and algorithm optimization.

1

Create the initial max-heap array

Create an integer array called heap with these exact values: {40, 30, 20, 15, 10, 5} and an integer variable called heap_size set to 6.

DSA C

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

Hint

Use int heap[] = {40, 30, 20, 15, 10, 5}; to create the array and int heap_size = 6; for the size.

2

Write the bubble_down function

Write a function called bubble_down that takes int heap[], int heap_size, and int index as parameters. It should restore the max-heap property by swapping the element at index with its largest child until the heap property is restored.

DSA C

int heap[] = {40, 30, 20, 15, 10, 5};
int heap_size = 6;

// Write bubble_down function here
// Your code here

Hint

Use recursion to swap the element at index with the largest child until no child is larger.

3

Extract the max element and bubble down

Write code to extract the max element from the heap by replacing heap[0] with heap[heap_size - 1], decreasing heap_size by 1, and calling bubble_down(heap, heap_size, 0).

DSA C

int heap[] = {40, 30, 20, 15, 10, 5};
int heap_size = 6;

void bubble_down(int heap[], int heap_size, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left  heap[largest]) {
        largest = left;
    }
    if (right  heap[largest]) {
        largest = right;
    }
    if (largest != index) {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;
        bubble_down(heap, heap_size, largest);
    }
}

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

Hint

Replace the root with the last element, reduce the heap size, then call bubble_down on index 0.

4

Print the heap after extraction

Write a for loop to print the elements of heap from index 0 to heap_size - 1 separated by spaces.

DSA C

int heap[] = {40, 30, 20, 15, 10, 5};
int heap_size = 6;

void bubble_down(int heap[], int heap_size, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left  heap[largest]) {
        largest = left;
    }
    if (right  heap[largest]) {
        largest = right;
    }
    if (largest != index) {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;
        bubble_down(heap, heap_size, largest);
    }
}

heap[0] = heap[heap_size - 1];
heap_size--;
bubble_down(heap, heap_size, 0);

// Print the heap elements separated by spaces
// Your code here

Hint

Use a for loop from 0 to heap_size - 1 and print each element with a space. End with a newline.

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