Heap Extract Min or Max Bubble Down in DSA Javascript - 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 should be done first. You use a heap data structure to keep tasks ordered by priority. When you remove the top task, you need to fix the heap so it still keeps 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 new root to restore the heap order.

📋 What You'll Learn

Create an array called heap with exact values representing a max heap

Create a variable called lastIndex to track the last element index

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

Print the heap array after extracting the max and bubbling down

💡 Why This Matters

🌍 Real World

Heaps are used in task scheduling, priority queues, 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 array called heap with these exact values: [50, 30, 40, 10, 20, 35]

DSA Javascript

// Create the heap array with the given values
// Your code here

Hint

Use const heap = [50, 30, 40, 10, 20, 35]; to create the heap array.

2

Create the lastIndex variable

Create a variable called lastIndex and set it to the last index of the heap array

DSA Javascript

const heap = [50, 30, 40, 10, 20, 35];
// Create lastIndex to track the last element index
// Your code here

Hint

Use let lastIndex = heap.length - 1; to get the last index.

3

Write the bubbleDown function

Write a function called bubbleDown that takes heap and startIndex as parameters. Inside, use a while loop to compare the current element with its children and swap with the larger child if needed, to restore max heap order.

DSA Javascript

const heap = [50, 30, 40, 10, 20, 35];
let lastIndex = heap.length - 1;

// Write bubbleDown function here
// Your code here

Hint

Use a while(true) loop and swap the current element with the larger child until no swaps are needed.

4

Extract max and bubble down, then print heap

Remove the max element at index 0 by replacing it with the last element in heap, then reduce lastIndex by 1. Call bubbleDown(heap, 0) to restore heap order. Finally, print the heap array sliced up to lastIndex + 1.

DSA Javascript

const heap = [50, 30, 40, 10, 20, 35];
let lastIndex = heap.length - 1;

function bubbleDown(heap, startIndex) {
    let index = startIndex;
    const length = heap.length;
    while (true) {
        let leftChild = 2 * index + 1;
        let rightChild = 2 * index + 2;
        let largest = index;

        if (leftChild  heap[largest]) {
            largest = leftChild;
        }
        if (rightChild  heap[largest]) {
            largest = rightChild;
        }
        if (largest === index) {
            break;
        }
        [heap[index], heap[largest]] = [heap[largest], heap[index]];
        index = largest;
    }
}

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

Hint

Replace the root with the last element, remove the last element, then call bubbleDown(heap, 0). Print the updated heap array.

Practice

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

easy

A. To remove the largest element from the heap

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

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

D. To swap the last element with the root without any further changes

Solution

1. Step 1: Understand extract-min in a min-heap

   Extracting the minimum removes the root, which breaks the heap property.

2. Step 2: Role of bubble down

   Bubble down moves the new root element down 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 C

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap by pushing root down after extract [OK]

Common Mistakes:

• Thinking bubble down inserts new elements
• Confusing bubble down with bubble up
• Assuming bubble down removes largest element

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in JavaScript during bubble down?

easy

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

B. swap(arr[i], arr[j]);

C. arr[i] = arr[j]; arr[j] = arr[i];

D. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

Solution

1. Step 1: Identify JavaScript swap syntax

   ES6 allows swapping with destructuring: [a, b] = [b, a].

2. Step 2: Check each option

   [arr[i], arr[j]] = [arr[j], arr[i]]; uses correct destructuring syntax. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; is valid but missing var or let for temp, so incomplete. Options A and C are incorrect syntax or logic.

3. Final Answer:

   [arr[i], arr[j]] = [arr[j], arr[i]]; -> Option A

4. Quick Check:

   Use destructuring swap in JS [OK]

Hint: Use ES6 destructuring for swap: [a,b]=[b,a] [OK]

Common Mistakes:

• Using undefined swap function
• Overwriting values without temp variable
• Incorrect assignment order causing same values

3. Given the min-heap array [2, 5, 3, 8, 10], after extracting the minimum and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 8, 10]

B. [5, 3, 8, 10]

C. [5, 8, 3, 10]

D. [3, 5, 10, 8]

Solution

1. Step 1: Extract min and replace root

   Remove 2 (root), move last element 10 to root: [10, 5, 3, 8]

2. Step 2: Bubble down 10

   Compare 10 with children 5 and 3. Smallest child is 3 at index 2. Swap 10 and 3: [3, 5, 10, 8]. Now 10 at index 2 has no children (indices 5 and 6 out of bounds), so stop.

3. Final Answer:

   [3, 5, 10, 8] -> Option D

4. Quick Check:

   Bubble down restores min-heap [OK]

Hint: Replace root with last, then swap down with smaller child [OK]

Common Mistakes:

• Not swapping with smallest child
• Forgetting to remove last element
• Swapping with larger child

4. Consider this bubble down code snippet for a max-heap extract operation:

function bubbleDown(arr, index) {
  let left = 2 * index + 1;
  let right = 2 * index + 2;
  let largest = index;
  if (left < arr.length && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < arr.length && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== index) {
    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    bubbleDown(arr, largest);
  }
}

What is the bug if the heap array is empty after extract and bubbleDown is called with index 0?

medium

A. Infinite recursion because largest never equals index

B. No bug; function handles empty array correctly

C. Accessing arr[0] causes undefined behavior on empty array

D. Swapping elements without checking array length

Solution

1. Step 1: Analyze empty array case

   If arr is empty, arr.length = 0, left and right indices are 1 and 2, both >= length, so no swaps.

2. Step 2: Check access at arr[index]

   No accesses occur because child indices out of bounds and && short-circuits prevent evaluating arr[largest]. Function handles empty array safely.

3. Final Answer:

   No bug; function handles empty array correctly -> Option B

4. Quick Check:

   Check array length before accessing index [OK]

Hint: Always check array length before accessing indices [OK]

Common Mistakes:

• Assuming recursion stops automatically
• Ignoring empty array edge case
• Not validating index bounds

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

hard

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

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

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

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

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

   Compare 35 with children 30 and 40. Largest child is 40 at index 2. Swap 35 and 40: [40, 30, 35, 10, 20]. Now 35 at index 2 has children beyond array length, so stop.

3. Final Answer:

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

4. Quick Check:

   Bubble down swaps with largest child in max-heap [OK]

Hint: Swap root with largest child until heap property restored [OK]

Common Mistakes:

• Swapping with smaller child
• Not moving last element to root
• Stopping bubble down too early