Understanding Heaps: A Powerful Data Structure for Priority Queues

You have a million tasks. You always need the highest-priority one next. Sorting the entire list every time a task arrives is O(n log n). A heap gives you the answer in O(1) and accepts new tasks in O(log n).

A heap is a binary tree with one rule: every parent node is smaller (min heap) or larger (max heap) than its children. The root is always the extreme value. You can get the min or max instantly.

Min Heap vs Max Heap

Min heap: The smallest value is always at the root. Used when you need the minimum element quickly -- Dijkstra's algorithm, job schedulers processing shortest tasks first.

Max heap: The largest value is always at the root. Used for things like priority queues where the highest-priority item goes first.

How It Works

Heaps are stored in a flat array. No pointers needed. For a node at index i:

• Left child: 2i + 1
• Right child: 2i + 2
• Parent: Math.floor((i - 1) / 2)

This array layout makes heaps cache-friendly and memory-efficient.

Implementation

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

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

  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  peek(): number | undefined {
    return this.heap[0];
  }

  size(): number {
    return this.heap.length;
  }

  private bubbleUp(index: number): void {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.heap[index] < this.heap[parent]) {
        [this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]];
        index = parent;
      } else {
        break;
      }
    }
  }

  private bubbleDown(index: number): void {
    while (true) {
      let smallest = index;
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }
      if (smallest !== index) {
        [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
        index = smallest;
      } else {
        break;
      }
    }
  }
}

const heap = new MinHeap();
heap.insert(5);
heap.insert(10);
heap.insert(3);
heap.insert(1);

console.log(heap.extractMin()); // 1
console.log(heap.extractMin()); // 3
console.log(heap.peek());       // 5

Performance

The O(n) build time is surprising. You might expect O(n log n), but the math works out because most nodes are near the bottom and barely need to move.

Where Heaps Show Up

• Priority queues: The primary use case. Process items by priority, not arrival order. OS task schedulers, event systems, and network packet prioritization all use heaps.
• Dijkstra's shortest path: A min heap efficiently selects the next unvisited vertex with the smallest tentative distance.
• Heapsort: Build a heap from the array, then repeatedly extract the min/max. O(n log n) guaranteed, no extra space needed (in-place variant). Not as fast as quicksort in practice due to cache behavior, but has a guaranteed worst case.
• Median finding: Use two heaps (a max heap for the lower half and a min heap for the upper half) to find the running median of a stream in O(log n) per insert.
• K-th largest/smallest: Maintain a heap of size k. Processing n elements takes O(n log k) instead of sorting the whole thing.

The Trade-off

Heaps are great at extracting the extreme element, but terrible at arbitrary lookups. Finding a specific value in a heap is O(n) -- you have to scan the whole thing. If you need both fast min/max and fast arbitrary access, you need a different structure (like a balanced BST or an indexed priority queue).

A heap does one thing exceptionally well: keep the most important element at the top. When that's your access pattern, nothing beats it.