Heaps and Priority Queues

A priority queue is the ADT: insert a key, pull the smallest (or largest). A binary heap is the usual implementation: a complete binary tree in an array, parent ≤ children (min-heap).

JS has no std heap. In the arena you may keep a sorted array and splice for n ≤ a few thousand, or write a small heap. In C++ it is priority_queue (max-heap by default — flip with greater<>). Python is heapq (min-heap).

USACO Silver already wants heaps for 'greedy with a bag of options' (Movie Festival II). Gold Dijkstra is the same extract-min.

Minimum cost to connect ropes — always merge two smallestjs

function connectRopes(lens) {
  const h = lens.slice().sort((a, b) => a - b);
  let cost = 0;
  while (h.length > 1) {
    const a = h.shift();
    const b = h.shift();
    const s = a + b;
    cost += s;
    // insert s back in order (O(n); use a real heap at n = 2e5)
    let i = 0;
    while (i < h.length && h[i] < s) i++;
    h.splice(i, 0, s);
  }
  return cost;
}

TRACE

Ropes [4, 3, 2, 6]. Always join the two shortest.

Bag

2, 3, 4, 6.

1 / 4

CHECK

Dijkstra uses a min-heap of (distance, node). Why not a sorted vector you re-sort after every relax?

WA modes:

- Max vs min. C++ priority_queue is a max-heap. Dijkstra with a max-heap explores large distances first and is wrong. - Stale entries. The lazy-Dijkstra pattern pushes a new pair instead of decreasing a key. Skip popped nodes whose distance is outdated (if (d !== dist[u]) continue). - Greedy without a proof. 'Always merge smallest' is Huffman / MST-adjacent and *is* optimal for connect-ropes. 'Always eat the largest stone' (last stone weight) is a different heap problem with its own exchange.

CHECK

Movie Festival II: k screens, maximize films. After sorting by end, what does the heap store?

Checks 0/2

Next lesson