Heap (priority queue) pattern: template and problems

When it applies

Use a heap when you repeatedly need the current best of a changing collection: the smallest pending job, the largest profit you can afford, the k-th largest value seen so far. Sorting once does not help when elements keep arriving or leaving; a heap keeps the best at the top for O(log n) per insertion or removal.

Two shapes cover most problems. Keep k: a min-heap of size k holds the k largest items, and its top is the k-th largest, in O(n log k). Always take the best available: push everything that has become eligible, pop the best, repeat; this is the core of Dijkstra, Huffman coding and most scheduling problems.

Signals: "k-th largest", "top k", "merge k sorted", "cheapest", "schedule", "at most k picks", "stream". If you only ever need the minimum once, a single scan is enough; the heap earns its keep when the question is asked again and again.

The template

Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.

import heapq

heap = []                              # heap[0] is always the smallest
for x in items:
    heapq.heappush(heap, x)            # O(log n)
    if len(heap) > k:
        heapq.heappop(heap)            # drop the smallest; the k largest remain
kth_largest = heap[0]

#include <queue>
// std::priority_queue is a max-heap; std::greater turns it into a min-heap.
std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
for (int x : items) {
    heap.push(x);                      // O(log n)
    if ((int)heap.size() > k) heap.pop();
}
int kthLargest = heap.top();

// PriorityQueue is a min-heap by default.
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : items) {
    heap.add(x);                       // O(log n)
    if (heap.size() > k) heap.poll();
}
int kthLargest = heap.peek();

// JavaScript has no built-in heap; this is the minimum you need.
const h = [];
const push = x => { 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]]; i = p; } };
const pop = () => { const top = h[0], last = h.pop();
  if (h.length) { h[0] = last; let i = 0;
    for (;;) { const l = 2 * i + 1, r = l + 1; let m = i;
      if (l < h.length && h[l] < h[m]) m = l; if (r < h.length && h[r] < h[m]) m = r;
      if (m === i) break; [h[m], h[i]] = [h[i], h[m]]; i = m; } }
  return top; };

use std::collections::BinaryHeap;
use std::cmp::Reverse;
// BinaryHeap is a max-heap; wrapping values in Reverse makes it a min-heap.
let mut heap = BinaryHeap::new();
for &x in items {
    heap.push(Reverse(x));
    if heap.len() > k { heap.pop(); }
}
let kth_largest = heap.peek().unwrap().0;

import qualified Data.Map.Strict as M
-- A Map from value to count is a priority queue: findMin, deleteMin and insert are O(log n).
push x = M.insertWith (+) x 1
popMin m = case M.findMin m of
  (v, 1) -> (v, M.delete v m)
  (v, c) -> (v, M.insert v (c - 1) m)

Problems

Medium15 min

Or sit a timed interview: a fixed window, limited submissions, and a report at the end.

Heap (priority queue)

When it applies

The template

Problems

The k-th largest value

Cheapest way to join ropes

Most capital from at most k projects