Implementing a Binary Min-Heap in TypeScript

Welcome back! In our last lesson, we tackled the Lowest Common Ancestor problem using a recursive strategy where information from child nodes was "bubbled up" the call stack to make a decision at the parent. This idea of moving information up or down a tree to maintain a certain property is a powerful one, and we'll see it again today in a completely new context.

This lesson introduces the binary heap, a specialized tree-based data structure. Unlike the binary search trees we've seen, heaps aren't designed for general-purpose searching. Instead, they are hyper-optimized for one specific task: providing immediate access to the minimum (or maximum) element. This makes them the perfect tool for building priority queues.

Our goal is to implement a binary min-heap from scratch in TypeScript, focusing on its two core operations: inserting a new element and extracting the minimum element. Mastering this is not just a great exercise; it's a common requirement in technical interviews and a building block for many advanced algorithms.

What is a Binary Heap?

A heap is a special kind of binary tree that must satisfy two strict properties. For a min-heap, these are:

1. Structural Property: It must be a complete binary tree. This means that all levels of the tree are completely filled, except possibly for the last level, which is filled from left to right without any gaps.
2. Order Property (Heap Property): The value of any given node must be less than or equal to the values of its children. This rule recursively ensures that the smallest element in the entire structure is always at the root of the tree.

A max-heap is the opposite, where every parent node is greater than or equal to its children, keeping the largest element at the root. We'll focus on the min-heap today.

To get a better feel for these properties, let's start with a foundational reading.

Implementing a Heap with an Array

While we think of heaps as trees, implementing them with Node objects and pointers is inefficient. Because of the complete tree property, we can represent a heap perfectly using a simple array. There are no gaps, so we can map each element's position in the array to its position in the tree using simple arithmetic.

For an element at a zero-based index i in the array:

• Its parent is at index: Math.floor((i - 1) / 2)
• Its left child is at index: 2 * i + 1
• Its right child is at index: 2 * i + 2

This array-based approach is memory-efficient and fast. The following video provides a great visual explanation of this mapping and the properties we've just discussed.

The insert Operation: Bubbling Up

How do we add a new element to the heap while maintaining both properties? The process involves two steps:

1. Maintain Structure: Add the new element to the end of the array. This corresponds to placing it in the first available spot on the bottom level of the tree, from left to right. This ensures the tree remains complete.
2. Restore Order: The new element might be smaller than its parent, violating the min-heap property. To fix this, we "bubble it up" (also called sift-up or heapify-up). We compare the new element with its parent and swap them if the child is smaller. We repeat this process, moving the element up the tree until it is no longer smaller than its parent, or until it reaches the root.

The next segment of the NoobCoder video provides an excellent, animated demonstration of this process.

The extractMin Operation: Bubbling Down

Extracting the minimum element is what makes a heap so useful. In a min-heap, the minimum is always at the root (index 0). But once we remove it, we need to restructure the heap.

1. Save the Minimum: Store the value at index 0. This is the value we'll return.
2. Maintain Structure: Take the last element from the array and move it to the root (index 0). Then, shrink the array by one. This leaves a "hole" at the end, not the beginning, keeping the tree complete.
3. Restore Order: The new root is likely larger than its children, violating the min-heap property. To fix this, we "bubble it down" (or sift-down, heapify-down). We compare the element with its children, find the smallest of the two children, and if the element is larger than its smallest child, we swap them. We repeat this process, moving the element down the tree until it is smaller than both of its children, or it becomes a leaf node.

Let's see this in action.

A Complete TypeScript Implementation

With the theory of "heapify-up" and "heapify-down" in place, we can now assemble a full MinHeap class in TypeScript. The implementation directly translates the logic we've just seen into code.

The helper methods for calculating parent/child indices are private, encapsulating the core logic of the array-based representation. The public methods add (insert) and poll (extract-min) orchestrate the heapify operations.

Here is a slightly simplified version of that code, with comments to reinforce the concepts:

class MinHeap {
  private heap: number[] = [];

  // Get the size of the heap
  public size(): number {
    return this.heap.length;
  }

  // Look at the smallest element without removing it
  public peek(): number | null {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  // Insert a new value into the heap
  public add(value: number): void {
    // 1. Add the element to the end of the array
    this.heap.push(value);
    // 2. Bubble it up to its correct position
    this._heapifyUp();
  }

  // Remove and return the smallest element
  public poll(): number | null {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop()!;

    // 1. Save the root (the minimum element)
    const root = this.heap[0];
    // 2. Move the last element to the root
    this.heap[0] = this.heap.pop()!;
    // 3. Bubble it down to its correct position
    this._heapifyDown();
    
    return root;
  }

  private _heapifyUp(): void {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      // If parent is smaller or equal, we're done
      if (this.heap[parentIndex] <= this.heap[index]) break;
      // Otherwise, swap with parent and continue up
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  private _heapifyDown(): void {
    let index = 0;
    const lastIndex = this.heap.length - 1;

    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let smallestChildIndex = leftChildIndex;

      // If no left child, we're at a leaf node and can't go down further
      if (leftChildIndex > lastIndex) break;

      // Check if right child exists and is smaller than the left
      if (rightChildIndex <= lastIndex && this.heap[rightChildIndex] < this.heap[leftChildIndex]) {
        smallestChildIndex = rightChildIndex;
      }

      // If current node is smaller than its smallest child, we're done
      if (this.heap[index] <= this.heap[smallestChildIndex]) break;

      // Otherwise, swap with smallest child and continue down
      [this.heap[index], this.heap[smallestChildIndex]] = [this.heap[smallestChildIndex], this.heap[index]];
      index = smallestChildIndex;
    }
  }
}

Both _heapifyUp and _heapifyDown traverse a path from the root to a leaf (or vice versa). Since a complete binary tree with $N$ nodes has a height of $O(\log N)$, both add and poll operations have a time complexity of $O(\log N)$. The peek operation is simply an array lookup at index 0, so it's $O(1)$.

Conclusion

In this lesson, we built a binary min-heap from the ground up. This powerful data structure is fundamental to solving a wide class of problems related to ordering, selection, and prioritization.

Key Takeaways:

• Heap Properties: A binary heap is a complete binary tree that satisfies the heap property (for a min-heap, parents are always smaller than or equal to children).
• Array Representation: Heaps are efficiently implemented using an array, with parent-child relationships calculated using index arithmetic.
• add (Insert): Add the element to the end of the array and heapify-up (bubble up) by swapping with its parent until the heap property is restored. This is an $O(\log N)$ operation.
• poll (Extract-Min): Replace the root with the last element, then heapify-down (bubble down) by swapping with the smaller of its two children until the heap property is restored. This is also an $O(\log N)$ operation.

In our next lesson, we will put our new MinHeap class to work by using it to solve a classic interview problem: finding the 'k' largest elements in a stream of data. This will demonstrate the practical power of a priority queue and why the heap is the perfect data structure to implement it.