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

Heap Extract Min or Max Bubble Down

📖 Scenario: Imagine you have a priority queue that helps you manage tasks by their importance. This queue is implemented as a heap, where the smallest (or largest) task always stays at the top. When you remove the top task, you need to rearrange the heap to keep it organized.

🎯 Goal: You will build the core part of a heap: extracting the top element (minimum or maximum) and then fixing the heap by moving the new root down to its correct position. This process is called bubble down.

📋 What You'll Learn

Create an array called heap with exact values representing a min-heap

Create a variable called heapSize to track the current size of the heap

Write a function called bubbleDown that moves the root element down to restore heap order

Write a function called extractMin that removes the smallest element and uses bubbleDown

Print the heap array after extraction to show the updated heap

💡 Why This Matters

🌍 Real World

Heaps are used in task scheduling, priority queues, and algorithms like Dijkstra's shortest path to efficiently get the highest or lowest priority item.

💼 Career

Understanding heap operations is important for software engineers working on performance-critical applications, system design, and algorithm optimization.

1

Create the initial min-heap array

Create an array called heap with these exact numbers in order: [3, 5, 8, 10, 15, 12]. Also create a variable called heapSize and set it to 6.

DSA Typescript

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

Hint

Think of heap as your task list arranged by priority. heapSize tells how many tasks are currently in the list.

2

Write the bubbleDown function

Write a function called bubbleDown that takes a parameter index. Inside, use a while loop to compare the element at index with its children at 2 * index + 1 and 2 * index + 2. Swap with the smallest child if needed and update index. Stop when no swaps are needed or children are out of heapSize bounds.

DSA Typescript

const heap = [3, 5, 8, 10, 15, 12];
let heapSize = 6;

// Write bubbleDown function below
# Your code here

Hint

Remember, bubble down means swapping the current element with the smaller of its children until the heap property is restored.

3

Write the extractMin function

Write a function called extractMin that removes and returns the smallest element from the heap. Replace the root with the last element in the heap, decrease heapSize by 1, then call bubbleDown(0) to fix the heap.

DSA Typescript

const heap = [3, 5, 8, 10, 15, 12];
let heapSize = 6;

function bubbleDown(index: number): void {
    while (true) {
        let left = 2 * index + 1;
        let right = 2 * index + 2;
        let smallest = index;

        if (left < heapSize && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < heapSize && heap[right] < heap[smallest]) {
            smallest = right;
        }

        if (smallest !== index) {
            [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
            index = smallest;
        } else {
            break;
        }
    }
}

// Write extractMin function below
# Your code here

Hint

Extracting the min means taking the root, replacing it with the last element, shrinking the heap, and fixing the order.

4

Print the heap after extraction

Call extractMin() and then print the heap array sliced up to heapSize to show the updated heap.

DSA Typescript

const heap = [3, 5, 8, 10, 15, 12];
let heapSize = 6;

function bubbleDown(index: number): void {
    while (true) {
        let left = 2 * index + 1;
        let right = 2 * index + 2;
        let smallest = index;

        if (left < heapSize && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < heapSize && heap[right] < heap[smallest]) {
            smallest = right;
        }

        if (smallest !== index) {
            [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
            index = smallest;
        } else {
            break;
        }
    }
}

function extractMin(): number | null {
    if (heapSize === 0) return null;
    const min = heap[0];
    heap[0] = heap[heapSize - 1];
    heapSize--;
    bubbleDown(0);
    return min;
}

// Call extractMin and print the updated heap
# Your code here

Hint

After removing the smallest element, print the heap array only up to the current heapSize to see the updated heap.