Heaps and priority queues

A heap is the structure you reach for whenever the honest description of a problem is "keep handing me the smallest (or most urgent) thing, while new things keep arriving". It is also the reason heapq and PriorityQueue exist, and the hidden engine inside Dijkstra's algorithm, schedulers and every "top k" question.

The problem it solves

Imagine a task scheduler. Jobs arrive constantly, each with a priority, and the worker always wants the most urgent one next. Three obvious approaches, all with a cost:

• An unsorted array. Adding is O(1), but finding the most urgent job means scanning everything: O(n) per pick.
• A sorted array. Picking is O(1), but every insert has to keep the order: O(n) to shift.
• Re-sorting before each pick. O(n log n) every time.

A heap sits in the middle and wins the mixed workload: insert in O(log n), read the minimum in O(1), remove the minimum in O(log n). It never fully sorts the data. It only maintains enough order to know what is on top.

Structure

A heap is a complete binary tree: every level is full except possibly the last, which fills from the left. That one shape constraint is what lets the whole thing live in a plain array with no node objects and no pointers.

Read the array level by level and you get the tree above. Relationships become arithmetic:

Check it: the node at index 4 (value 4) has parent floor((4 - 1) / 2) = 1 (value 3), and index 1's children are 2 * 1 + 1 = 3 and 2 * 1 + 2 = 4. This is the same level-order layout a breadth-first tree walk produces, used as the real storage instead of a by-product.

The invariant: parent beats children

A heap enforces exactly one rule, everywhere at once. In a min-heap, every parent is less than or equal to both of its children. (Flip the comparison for a max-heap.)

Notice what the rule does not say: nothing compares left to right, or one cousin to another. That is much weaker than a binary search tree's ordering, and precisely why a heap is cheaper to maintain: an insert or removal only ever repairs one path from the root to a leaf, never the whole shape.

That single weak guarantee still answers one question instantly. The minimum is always at index 0, so peek() is O(1).

push: bubble up

New values are appended at the end of the array, the next free leaf, which keeps the tree complete. The new value might now be smaller than its parent, so it bubbles up, swapping upward while it is smaller.

pop: sift down

Removing the minimum leaves a hole at the root. Filling it by shifting everything would break the shape, so the trick is to take the last element, put it at the root, and let it sift down, always swapping with the smaller child, until the rule holds again.

Both operations touch one root-to-leaf path. A complete tree with n nodes has height about log n, so push and pop are O(log n), and peek is O(1).

A complete min-heap

class MinHeap {
  #data = [];

  get size() { return this.#data.length; }
  peek() { return this.#data[0]; }

  push(val) {
    this.#data.push(val);
    this.#siftUp(this.#data.length - 1);
  }

  pop() {
    if (this.#data.length === 0) return undefined;
    const top = this.#data[0];
    const last = this.#data.pop();
    if (this.#data.length > 0) {
      this.#data[0] = last;
      this.#siftDown(0);
    }
    return top;
  }

  #siftUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.#data[i] >= this.#data[parent]) break;
      [this.#data[i], this.#data[parent]] = [this.#data[parent], this.#data[i]];
      i = parent;
    }
  }

  #siftDown(i) {
    const n = this.#data.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < n && this.#data[l] < this.#data[smallest]) smallest = l;
      if (r < n && this.#data[r] < this.#data[smallest]) smallest = r;
      if (smallest === i) break;
      [this.#data[i], this.#data[smallest]] = [this.#data[smallest], this.#data[i]];
      i = smallest;
    }
  }
}

Two details that trip people up. In pop, take the last element before checking whether anything is left, or a one-element heap breaks. And in siftDown, compare against both children and swap with the smaller one: swapping with the larger child would break the rule for the other side.

Complexity at a glance

Why "k largest" needs a small heap, not a big sort

The obvious answer to "find the k largest values" is to sort everything and take the last k. That is O(n log n): you fully order data you do not need ordered, just to read a handful off one end.

The heap holds the k best so far, and its minimum is the entry ticket: a new value must beat the weakest of the current top k to get in.

function kLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    if (heap.size < k) heap.push(n);
    else if (n > heap.peek()) { heap.pop(); heap.push(n); }
  }
  const result = [];
  while (heap.size) result.push(heap.pop());
  return result.reverse(); // largest first
}

Each of the n values costs at most one O(log k) heap operation, against a heap that never grows past k. Total O(n log k), and O(k) memory. When k is small relative to n (the top 10 scores out of a million) that is an order of magnitude cheaper than a full sort, and it works on a stream you cannot hold in memory.

The same shape solves top-k frequent elements: count with a hash table first, then keep a size-k heap of the (count, value) pairs. It also solves the k-th largest element (the heap's minimum once it is full), and merging k sorted lists (push each list's head, pop the smallest, push that list's next).

Min-heap, max-heap, and custom priorities

• Max-heap. Flip the comparison. In a language with only a min-heap, such as Python's heapq, push the negated value (-x) and negate again on the way out.
• Objects with a priority. Store [priority, item] pairs (tuples in Python) and compare on the first element, or pass a comparator to your heap.
• Tie-breaking. If two items have the same priority and the order matters, add a running counter as a second sort key. Otherwise a heap gives no stability guarantee.
• JavaScript has no built-in heap. You either write one (as above), use a library, or, for small inputs, sort. This is why heap questions in JavaScript interviews expect you to implement it.

Where heaps are used in real systems

Heaps you already use

• Python `heapq` (heappush, heappop, nlargest, nsmallest) and `queue.PriorityQueue`.
• Java `PriorityQueue` and C++ `std::priority_queue`.
• Timer wheels and timer heaps inside runtimes and job libraries decide which callback is due next.
• Database engines use heaps for ORDER BY ... LIMIT k: they keep a size-k heap instead of sorting the whole table.
• Kubernetes and OS schedulers rely on priority queues to choose the next thing to run.

Heap or binary search tree

If you only ever need "the next smallest", a heap is simpler, faster in practice and more compact. If you also need lookups, ranges or sorted iteration, use a tree.

When not to use a heap

• You need ordered iteration. A heap is not sorted; only the top is meaningful. Popping everything gives sorted order, but destroys the heap.
• You need to find or update arbitrary items. Searching is O(n). "Decrease the priority of this item" needs extra bookkeeping (a map from item to index), or lazy deletion where stale entries are skipped when they surface.
• A single min or max is enough. If you scan once and only need the smallest, a variable is simpler than a heap.
• You need all n items sorted anyway. Just sort. A heap only pays off when you need part of the order, or when data keeps arriving.

What interviewers ask

• "Implement a min-heap." push, pop, peek, with the index math and both sift directions.
• "Find the k largest (or the k-th largest) elements." A size-k min-heap, O(n log k). Say why not a sort.
• "Top k frequent elements." A hash table for counts, then a heap or a bucket sort.
• "Merge k sorted lists." A heap of the current heads, O(N log k).
• "Find the running median." Two heaps balanced in size.
• "Why is building a heap O(n) and not O(n log n)?" Most nodes are near the leaves and sift down only a step or two. The sum of the work converges to O(n).
• "Heap versus sorted array versus BST?" The table above, in one breath.

The mistake to avoid

Swapping the new root with the larger child in siftDown, or forgetting to check that a child index is inside the array before reading it. Either one corrupts the invariant quietly: the heap still returns plausible values for a while, then hands out the wrong minimum on a specific input. Always compare with both children, choose the smaller, and guard l < n and r < n.

"Heap" is the implementation and "priority queue" is the interface. Whenever a problem says "repeatedly take the best remaining item while new ones arrive", or "we only care about the top k", the structure it is asking for is a heap.