Heaps

A heap answers one question fast: "what’s the smallest (or largest) thing right now?" It doesn’t keep everything sorted — that would be overkill. It only maintains enough order to keep the extreme element at the top, which is all a priority queue needs.

The magic is the shape. A binary heap is a complete binary tree — every level is full except possibly the last, which fills left to right. Because the shape is so regular, you don’t need actual tree nodes and pointers: you can pack the whole thing into a plain array, and simple index math gives you the parent and children of any node.

An array is a tree

Store the tree level by level in an array. For the node at index i: its left child is at 2i + 1, its right child at 2i + 2, and its parent at ⌊(i − 1) / 2⌋. No pointers, great cache locality. The heap property is the only invariant: in a min-heap, every parent is ≤ both children (a max-heap flips the comparison). Note this is weaker than sorted — siblings have no ordering between them.

Sift up, sift down

Two repair operations keep the heap property intact. Sift up: after inserting at the end, bubble the new value upward while it’s smaller than its parent. Sift down: to remove the root, move the last element to the top, then sink it downward, swapping with its smaller child until order is restored. Each touches at most the tree’s height, so both are O(log n).

class MinHeap {
  constructor() { this.h = [] }
  peek() { return this.h[0] }
  push(x) {
    const h = this.h
    h.push(x)
    let i = h.length - 1
    while (i > 0) {
      const p = (i - 1) >> 1
      if (h[p] <= h[i]) break
      [h[p], h[i]] = [h[i], h[p]] // sift up
      i = p
    }
  }
  pop() {
    const h = this.h
    const top = h[0]
    const last = h.pop()
    if (h.length) {
      h[0] = last
      let i = 0
      const n = h.length
      while (true) {
        let s = i
        const l = 2 * i + 1, r = 2 * i + 2
        if (l < n && h[l] < h[s]) s = l
        if (r < n && h[r] < h[s]) s = r
        if (s === i) break
        [h[i], h[s]] = [h[s], h[i]] // sift down
        i = s
      }
    }
    return top
  }
}

Heapsort

A heap gives you a sorting algorithm almost for free. Heapify the array in O(n), then repeatedly extract the max and place it at the end — n extractions at O(log n) each gives O(n log n) overall, with O(1) extra space since it sorts in place. It’s not as cache-friendly as quicksort in practice, but it has no bad-case blowup: heapsort is O(n log n) even in the worst case.

Top-K and streaming

The killer application is finding the K largest (or smallest) elements. Keep a min-heap of size k: push each element, and whenever the heap exceeds k, pop the smallest. What remains are the K largest — in O(n log k) time and O(k) space, without ever sorting the full input. This scales to streams too large to hold in memory.

function topK(nums, k) {
  const heap = new MinHeap()
  for (const x of nums) {
    heap.push(x)
    if (heap.h.length > k) heap.pop() // drop the smallest
  }
  return heap.h // the k largest (unordered)
}

When to reach for a heap

• You need repeated access to the min or max while the set keeps changing — a priority queue.
• You’re running Dijkstra or Prim — both pull the next-cheapest edge/node from a heap.
• You want the top-K of a huge or streaming dataset without a full sort.
• You need a merge of k sorted lists — a heap of k heads does it in O(n log k).
• Avoid it when you need full ordering or arbitrary lookups — a balanced BST or sorted array fits better.