🏔️ Heap / Priority Queue

A learning sheet — when you repeatedly need the smallest or largest thing (but not everything sorted), a heap gives it to you in O(log n).

🧠 1 · How to think (and invent it)

A heap is a complete binary tree kept in a flat array, obeying one rule — the heap property: every parent is ≤ its children (min-heap) or ≥ (max-heap). That's it. It does not keep things fully sorted; it keeps just enough order that the extreme is always at the root. Peek is O(1); insert and extract are O(log n) (one walk up or down the tree height).

Because the array is implicit, the tree links are pure arithmetic: for index i, parent = (i−1)/2, children = 2i+1 and 2i+2. Two operations maintain the property: sift-up (after a push, bubble the newcomer up) and sift-down (after replacing the root, sink it down).

Watch it get invented — the k largest of a stream

1. Start brute. Sort all n → O(n log n), and impossible if the data streams in and doesn't fit in memory.
2. Spot the structure. You only ever need the k best so far. A newcomer matters only if it beats the smallest of those k — so you need fast access to that smallest.
3. The leap (and the twist). Keep a min-heap of size k. Push each number; if the heap exceeds k, pop the minimum. Counter-intuitively, you use a min-heap to track the largest k — its root is the weakest survivor, i.e. the k-th largest.
4. Payoff. O(n log k) time, O(k) space, works on an infinite stream.

Stream [3,1,5,2,4], k = 2 → the heap ends holding the top 2 = {4, 5}; its root 4 is the k-th largest.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The five core patterns

JS has no built-in PQ, so §4.1 gives a tiny correct MinHeap the others reuse. Each pattern: a one-liner, a 🔑 invariant, a template, a 🎤 interview lens.

4.1 · Mechanics — sift-up & sift-down

“Push and bubble up; pop the root, move the last up, and sink it down.”

class MinHeap<T> {
  private h: T[] = [];
  constructor(private less: (a: T, b: T) => boolean) {}   // less(a,b)=a<b → min-heap
  size() { return this.h.length; }
  peek(): T { return this.h[0]; }
  push(x: T) { this.h.push(x); this.up(this.h.length - 1); }
  pop(): T {
    const top = this.h[0], last = this.h.pop()!;
    if (this.h.length) { this.h[0] = last; this.down(0); }
    return top;
  }
  private up(i: number) {
    while (i > 0) { const p = (i - 1) >> 1; if (!this.less(this.h[i], this.h[p])) break;
      [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
  }
  private down(i: number) {
    const n = this.h.length;
    while (true) {
      let s = i; const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.less(this.h[l], this.h[s])) s = l;
      if (r < n && this.less(this.h[r], this.h[s])) s = r;
      if (s === i) break;
      [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s;
    }
  }
}
// a MAX-heap is just a MinHeap with the comparison flipped:
const maxHeap = () => new MinHeap<number>((a, b) => a > b);

4.2 · Top-K / k-th

“For the k largest, keep a MIN-heap of size k — its root is the k-th largest.”

Setup: the heap of size k always holds the best k seen, and its root is the weakest of them — exactly the threshold a newcomer must beat.

// k-th largest in an array (or stream)
function kthLargest(nums: number[], k: number): number {
  const heap = new MinHeap<number>((a, b) => a < b);   // MIN-heap (note!)
  for (const x of nums) {
    heap.push(x);
    if (heap.size() > k) heap.pop();    // drop the smallest → keep the largest k
  }
  return heap.peek();                    // root = k-th largest; heap = the top k
}

4.3 · K-way merge

“Heap the k current heads; pop the smallest, push its successor.”

Setup: to merge k sorted sequences, the global next-smallest is always the min of the k front elements — exactly what a min-heap of size k serves.

// Merge k sorted linked lists
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const heap = new MinHeap<ListNode>((a, b) => a.val < b.val);
  for (const l of lists) if (l) heap.push(l);
  const dummy = new ListNode(0); let tail = dummy;
  while (heap.size()) {
    const node = heap.pop();
    tail.next = node; tail = node;
    if (node.next) heap.push(node.next);   // pull the next from that list
  }
  return dummy.next;
}

4.4 · Two heaps — running median & balance

“Max-heap holds the lower half, min-heap the upper; the median sits between.”

Setup: split the data into a lower half (a max-heap, so its top is the lower-half max) and an upper half (a min-heap, top = upper-half min). Keep the sizes balanced and the median is at the tops.

class MedianFinder {
  private lo = new MinHeap<number>((a, b) => a > b);  // MAX-heap (lower half)
  private hi = new MinHeap<number>((a, b) => a < b);  // MIN-heap (upper half)
  addNum(x: number) {
    this.lo.push(x);
    this.hi.push(this.lo.pop());                     // pass lo's max into hi (keeps lo ≤ hi)
    if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop()); // rebalance: lo ≥ hi
  }
  findMedian(): number {
    return this.lo.size() > this.hi.size()
      ? this.lo.peek()
      : (this.lo.peek() + this.hi.peek()) / 2;
  }
}

4.5 · Greedy driven by a heap

“Repeatedly pull the best available option; push back what it spawns.”

Setup: many scheduling/simulation problems reduce to "always act on the current most-urgent / cheapest / earliest-ending item" — a heap serves that item in O(log n).

// Meeting Rooms II — fewest rooms needed
function minMeetingRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);                 // by start
  const ends = new MinHeap<number>((a, b) => a < b);     // min-heap of end times
  let rooms = 0;
  for (const [start, end] of intervals) {
    if (ends.size() && ends.peek() <= start) ends.pop();  // a room freed up
    ends.push(end);
    rooms = Math.max(rooms, ends.size());                // peak concurrency
  }
  return rooms;
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

// 2402 Meeting Rooms III — free rooms (by index) + busy rooms (by end time, then index)
function mostBooked(n: number, meetings: number[][]): number {
  meetings.sort((a, b) => a[0] - b[0]);
  const free = new MinHeap<number>((a, b) => a < b);
  for (let r = 0; r < n; r++) free.push(r);
  const busy = new MinHeap<[number, number]>((a, b) => a[0] < b[0] || (a[0] === b[0] && a[1] < b[1]));   // [end, room]
  const used: number[] = new Array(n).fill(0);
  for (const [s, e] of meetings) {
    while (busy.size() && busy.peek()[0] <= s) free.push(busy.pop()[1]);   // release rooms that finished
    let room: number, end: number;
    if (free.size()) { room = free.pop(); end = e; }
    else { const [t, r] = busy.pop(); room = r; end = t + (e - s); }       // delayed: keeps its DURATION
    busy.push([end, room]); used[room]++;
  }
  let best = 0;
  for (let r = 1; r < n; r++) if (used[r] > used[best]) best = r;          // ties → lowest index
  return best;
}

// 358 Rearrange String k Distance Apart — max-heap by count + cooldown queue
function rearrangeString(s: string, k: number): string {
  if (k <= 1) return s;
  const cnt = new Map<string, number>();
  for (const ch of s) cnt.set(ch, (cnt.get(ch) ?? 0) + 1);
  const heap = new MinHeap<[number, string]>((a, b) => a[0] > b[0] || (a[0] === b[0] && a[1] < b[1]));   // most frequent first
  for (const [ch, c] of cnt) heap.push([c, ch]);
  const wait: [number, string][] = []; let res = '';
  while (heap.size()) {
    const [c, ch] = heap.pop(); res += ch;
    wait.push([c - 1, ch]);
    if (wait.length >= k) { const [c2, ch2] = wait.shift()!; if (c2 > 0) heap.push([c2, ch2]); }   // usable again after k placements
  }
  return res.length === s.length ? res : '';
}

// 1353 Maximum Number of Events That Can Be Attended — earliest deadline first
function maxEvents(events: number[][]): number {
  events.sort((a, b) => a[0] - b[0]);
  const heap = new MinHeap<number>((a, b) => a < b);                       // end days
  let i = 0, day = 0, count = 0;
  while (i < events.length || heap.size()) {
    if (!heap.size()) day = Math.max(day, events[i][0]);                   // jump over empty days
    while (i < events.length && events[i][0] <= day) heap.push(events[i++][1]);
    while (heap.size() && heap.peek() < day) heap.pop();                   // expired
    if (heap.size()) { heap.pop(); count++; }                              // attend the one ending soonest
    day++;
  }
  return count;
}

// 857 Minimum Cost to Hire K Workers — sort by wage/quality, heap keeps the K smallest qualities
function mincostToHireWorkers(quality: number[], wage: number[], k: number): number {
  const workers = quality.map((q, i) => ({ q, r: wage[i] / q })).sort((a, b) => a.r - b.r);
  const heap = new MinHeap<number>((a, b) => a > b);                       // max-heap of qualities
  let sumQ = 0, best = Infinity;
  for (const w of workers) {
    heap.push(w.q); sumQ += w.q;
    if (heap.size() > k) sumQ -= heap.pop();                               // drop the LARGEST quality
    if (heap.size() === k) best = Math.min(best, w.r * sumQ);              // w.r is the group rate (max ratio so far)
  }
  return best;
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• mechanics MinHeap (push/pop, sift-up/down)
• top-k kthLargest (min-heap of size k)
• k-way mergeKLists
• two heaps MedianFinder
• greedy minMeetingRooms

For each: write "which heap (min/max), what's at the root, what invariant" as a comment before the code.