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.