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.

Practice

1. What is the main purpose of the bubble down operation in a min-heap after extracting the minimum element?

easy

A. To delete the last element in the heap

B. To insert a new element at the bottom of the heap

C. To swap the minimum element with the maximum element

D. To restore the heap property by moving the root element down to its correct position

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, the last element replaces the root.

2. Step 2: Apply bubble down to restore heap

   The bubble down moves this element down the tree to restore the min-heap property.

3. Final Answer:

   To restore the heap property by moving the root element down to its correct position -> Option D

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap after removing root [OK]

Common Mistakes:

• Confusing bubble down with insertion
• Thinking bubble down swaps min and max
• Assuming bubble down deletes elements

2. Which of the following TypeScript code snippets correctly swaps two elements in a heap array during bubble down?

easy

A. heap[i], heap[j] = heap[j], heap[i];

B. const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp;

C. swap(heap[i], heap[j]);

D. heap[i] = heap[j]; heap[j] = heap[i];

Solution

1. Step 1: Check valid swap syntax in TypeScript

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses a temporary variable to swap two elements correctly.

2. Step 2: Identify incorrect syntax in other options

   heap[i], heap[j] = heap[j], heap[i]; uses Python-style unpacking (invalid in TypeScript), C calls undefined function, D overwrites values incorrectly.

3. Final Answer:

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in TypeScript [OK]

Hint: Use temp variable for swapping in TypeScript [OK]

Common Mistakes:

• Using Python tuple swap syntax in TypeScript
• Calling undefined swap function
• Overwriting values without temp variable

3. Consider the min-heap array [2, 5, 3, 10, 7]. After extracting the minimum element and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 7, 10]

B. [3, 7, 5, 10]

C. [5, 7, 3, 10]

D. [7, 5, 3, 10]

Solution

1. Step 1: Remove root and replace with last element

   Remove 2, replace root with 7: [7, 5, 3, 10]

2. Step 2: Bubble down 7 to restore min-heap

   Compare 7 with children 5 and 3; swap with smallest child 3: [3, 5, 7, 10]

3. Final Answer:

   [3, 5, 7, 10] -> Option A

4. Quick Check:

   Extract min and bubble down result = [3, 5, 7, 10] [OK]

Hint: Replace root with last, then bubble down [OK]

Common Mistakes:

• Not replacing root with last element
• Swapping with wrong child during bubble down
• Forgetting to remove last element

4. The following TypeScript code attempts to bubble down an element in a max-heap but does not work correctly. What is the main bug?

function bubbleDown(heap: number[], i: number) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let largest = i;

  if (left < heap.length && heap[left] > heap[largest]) {
    largest = left;
  }
  if (right < heap.length && heap[right] > heap[largest]) {
    largest = right;
  }

  if (largest !== i) {
    heap[i] = heap[largest];
    heap[largest] = heap[i];
    bubbleDown(heap, largest);
  }
}

medium

A. Swapping elements overwrites values incorrectly without a temporary variable

B. The indices for left and right children are calculated incorrectly

C. The recursive call should be bubbleUp instead of bubbleDown

D. The condition to check children is reversed for max-heap

Solution

1. Step 1: Analyze swap logic in code

   The swap uses heap[i] = heap[largest]; heap[largest] = heap[i]; which overwrites heap[i] before assigning heap[largest].

2. Step 2: Identify correct swap method

   Swapping requires a temporary variable to avoid overwriting values.

3. Final Answer:

   Swapping elements overwrites values incorrectly without a temporary variable -> Option A

4. Quick Check:

   Swap needs temp variable to avoid overwrite [OK]

Hint: Always use temp variable when swapping array elements [OK]

Common Mistakes:

• Overwriting values during swap without temp
• Confusing bubbleDown with bubbleUp
• Incorrect child index calculations

5. You have a max-heap represented by the array [50, 30, 40, 10, 20, 35]. After extracting the maximum element and performing bubble down, what is the final heap array?

hard

A. [35, 30, 40, 10, 20]

B. [40, 30, 20, 10, 35]

C. [40, 30, 35, 10, 20]

D. [30, 20, 35, 10, 40]

Solution

1. Step 1: Remove max (root) and replace with last element

   Remove 50, replace root with 35: [35, 30, 40, 10, 20]

2. Step 2: Bubble down 35 to restore max-heap

   Compare 35 with children 30 and 40; swap with largest child 40: [40, 30, 35, 10, 20]

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option C

4. Quick Check:

   Extract max and bubble down result = [40, 30, 35, 10, 20] [OK]

Hint: Replace root with last, then bubble down largest child [OK]

Common Mistakes:

• Swapping with wrong child during bubble down
• Not removing last element after replacement
• Confusing min-heap bubble down with max-heap