Min-Heap Implementation

Concept

Because JavaScript does not provide a native Heap, senior interviewers will occasionally ask you to build a Min-Heap from scratch using an Array.

You only need to memorize two core algorithmic maneuvers: Bubble Up (for Insertion) and Bubble Down (for Deletion).

1. Insertion (Bubble Up)

When a new item is added to the Heap, it is appended to the absolute end of the array (to preserve the Complete Tree shape).
However, this new item might be smaller than its Parent, violating the Min-Heap property.

The Fix: We “Bubble Up”. We compare the new item to its Parent. If the new item is smaller, they swap places. We repeat this process upwards until the item is larger than its Parent (or it hits the Root).

// Inside the MinHeap class...

insert(val: number): void {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
}

private bubbleUp(index: number): void {
    while (index > 0) {
        // Find the parent's index
        const parentIndex = Math.floor((index - 1) / 2);
        
        // If the child is >= the parent, order is restored! Stop bubbling.
        if (this.heap[index] >= this.heap[parentIndex]) break;
        
        // Otherwise, they are out of order. Swap them!
        this.swap(index, parentIndex);
        
        // Move our pointer up to the parent's old spot and repeat
        index = parentIndex;
    }
}

2. Deletion (Bubble Down / Sink Down)

The only item you are allowed to delete in a Heap is the Root (the absolute minimum at index 0).

If you just shift() the first item out of the array, every single subsequent item shifts left by one index. This completely destroys the mathematical 2i + 1 parent-child relationships, corrupting the entire tree!

The Fix:

1. Swap the Root with the absolute last item in the array.
2. pop() the last item off (safely removing the true minimum).
3. Now, the new Root is likely a massive, incorrect number. We must “Bubble Down” (Sink Down) by comparing it to its two children. We swap it with the smaller of the two children until order is restored.

extractMin(): number | null {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop()!;
    
    // Save the true minimum to return later
    const min = this.heap[0];
    
    // 1. Move the last leaf to the Root
    this.heap[0] = this.heap.pop()!;
    
    // 2. Sink it down to its correct spot
    this.bubbleDown(0);
    
    return min;
}

private bubbleDown(index: number): void {
    const length = this.heap.length;
    
    while (true) {
        let leftChildIndex = 2 * index + 1;
        let rightChildIndex = 2 * index + 2;
        let smallestIndex = index;

        // Is the Left child smaller than the current node?
        if (leftChildIndex < length && this.heap[leftChildIndex] < this.heap[smallestIndex]) {
            smallestIndex = leftChildIndex;
        }

        // Is the Right child even smaller than the Left child?
        if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallestIndex]) {
            smallestIndex = rightChildIndex;
        }

        // If the current node is already the smallest, we are done!
        if (smallestIndex === index) break;

        // Otherwise, swap with the smaller child and repeat
        this.swap(index, smallestIndex);
        index = smallestIndex;
    }
}

Interview Questions

Q: In the bubbleDown function, why must we explicitly find the “smaller of the two children”? Why can’t we just swap with the Left child if the Left child is smaller?
A: Imagine the Parent is 10, the Left child is 5, and the Right child is 2.
If we blindly swapped 10 with the Left child (5), the new Parent would be 5, and the Right child would still be 2. This violates the Min-Heap property (Parent 5 is NOT smaller than Right child 2).
By strictly selecting the absolute minimum of the three nodes (2), we guarantee that the new Parent (2) is mathematically smaller than both its Left child (5) and its new Right child (10).