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

Heap Extract Min or Max Bubble Down

📖 Scenario: You are managing a priority queue using a binary heap stored in an array. You want to remove the top element (minimum for min-heap or maximum for max-heap) and then restore the heap property by bubbling down the new root element.

🎯 Goal: Build a C++ program that extracts the root element from a heap array and restores the heap property by bubbling down the new root.

📋 What You'll Learn

Create an integer array called heap with the exact values: {10, 15, 20, 17, 25}

Create an integer variable called heap_size and set it to 5

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

Write code to extract the minimum element (root) from the heap, replace it with the last element, reduce heap_size, and call bubbleDown on the root

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

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

Create an integer array called heap with the exact values {10, 15, 20, 17, 25} and an integer variable called heap_size set to 5.

DSA C++

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

Hint

Use int heap[] = {10, 15, 20, 17, 25}; and int heap_size = 5;.

2

Write the bubbleDown function

Write a function called bubbleDown that takes parameters int heap[], int heap_size, and int index. The function should restore the min-heap property by bubbling down the element at index until the heap property is satisfied.

DSA C++

int heap[] = {10, 15, 20, 17, 25};
int heap_size = 5;

// Write bubbleDown function below
// Your code here

Hint

Use recursion or a loop to swap the element at index with the smaller child until the min-heap property is restored.

3

Extract the minimum element and bubble down

Write code to extract the minimum element from the heap by replacing the root with the last element, decreasing heap_size by 1, and calling bubbleDown on index 0.

DSA C++

int heap[] = {10, 15, 20, 17, 25};
int heap_size = 5;

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

    if (left < heap_size && heap[left] < heap[smallest]) {
        smallest = left;
    }
    if (right < heap_size && heap[right] < heap[smallest]) {
        smallest = right;
    }
    if (smallest != index) {
        int temp = heap[index];
        heap[index] = heap[smallest];
        heap[smallest] = temp;
        bubbleDown(heap, heap_size, smallest);
    }
}

// Extract min and bubble down
// Your code here

Hint

Replace the root with the last element, reduce heap_size, then call bubbleDown 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[] = {10, 15, 20, 17, 25};
int heap_size = 5;

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

    if (left < heap_size && heap[left] < heap[smallest]) {
        smallest = left;
    }
    if (right < heap_size && heap[right] < heap[smallest]) {
        smallest = right;
    }
    if (smallest != index) {
        int temp = heap[index];
        heap[index] = heap[smallest];
        heap[smallest] = temp;
        bubbleDown(heap, heap_size, smallest);
    }
}

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

// Print the heap elements
// Your code here

Hint

Use a for loop from 0 to heap_size - 1 and print each element followed by a space.