Heaps (priority queues)

The idea#

Picture a single-elimination bracket taped to the gym wall. The winner sits in the top slot. When a player leaves, you only replay the matches on the path from that slot down to an empty one.

A heap is a complete binary tree stored in an array. The root is the minimum, or the maximum if you flip the order. Push and pop are O(log n), peek is O(1), and building a heap from an array by sifting down from the middle is O(n). A top-k heap that never grows past k items costs O(n log k). JavaScript has no built-in heap. You write the class from memory.

The array has no holes. Index 0 is the root, the parent of i is (i - 1) >> 1, and the children are 2i + 1 and 2i + 2. Sift up bubbles a new item toward the root while it outranks its parent. Sift down drops a replacement until both children lose to it. When cmp(a, b) < 0, a has the higher priority. Pass (a, b) => b - a and the same class is a max-heap.

You rarely need every element in order. You need the current winner, or the k best. A min-heap of size k holds the k largest values seen so far, and its root is the smallest of those k, which is the kth largest overall. Evict when the size passes k. That is O(log k) per item.

Why it matters#

The phrases are k largest, k smallest, top k, kth, merge k sorted lists, running median, schedule by priority, closest k, and most frequent first. Sorting the whole input is O(n log n). A heap of size k answers the real question in O(n log k).

Two heaps split a stream. The lower half is a max-heap, so its root is the biggest of the small numbers. The upper half is a min-heap, so its root is the smallest of the big numbers. Keep the sizes within one. The median is the root of the bigger half, or the average of the two roots. Add is O(log n). Reading the median is O(1).

A k-way merge holds one head from each sorted array, tagged with which array it came from. Pop the smallest, push that array's next value, O(log k) per element. A to-do list you only read from the top is the same bargain: insert in O(log n), peek in O(1). Say the index formula out loud. If you cannot place a node in the array, you do not have the structure yet.

A small example#

function kthLargest(nums, k) {  const h = [];  const up = (i) => {    while (i > 0 && h[i] < h[(i - 1) >> 1]) {      const p = (i - 1) >> 1;      [h[i], h[p]] = [h[p], h[i]];      i = p;    }  };  const down = (i) => {    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) return;    [h[i], h[m]] = [h[m], h[i]];    down(m);  };  for (const x of nums) {    h.push(x);    up(h.length - 1);    if (h.length > k) { h[0] = h.pop(); if (h.length) down(0); }  }  return h[0];}const third = kthLargest([3, 2, 1, 5, 6, 4], 3);

third is 4. The min-heap never keeps more than the three largest values, and the root is the smallest of those three.

What the code below is doing#

Section 1 is the heap class. The comparator defaults to a min-heap. Push sifts up. Pop moves the last item to the root and sifts down. Peek is the root. Building by repeated push is O(n log n). Heapify in O(n), sifting down from (n >> 1) - 1 to 0, is the version to name even though this class builds by pushing.

Section 2 finds the kth largest with a min-heap of size k. Pop when the size passes k. The root is the answer. O(n log k) time, O(k) space. Section 3 is the top k frequent values: a frequency map, then a min-heap of [count, value] capped at k. Section 4 merges k sorted arrays. The heap holds [value, arrayIdx, elemIdx]. Pop the minimum and push that array's successor. O(N log k) for N total elements.

Section 5 is the running median. A max-heap keeps the lower half, a min-heap the upper half, and the sizes stay within one. Add is O(log n), median is O(1). Section 6 keeps the k closest points to the origin in a max-heap by distance, size k, so the farthest of the survivors is easy to evict.

Section 7 is the task scheduler in its counting form. Idle slots are (maxFreq - 1) * (n + 1) + countOfMax, and the answer is the larger of that and the number of tasks. O(n) time, O(26) space. A heap would place tasks one by one. The formula skips the simulation. Section 8 is meeting rooms: sort by start, keep a min-heap of end times, and pop when the earliest end is at or before the next start. The heap's size is the number of rooms. O(n log n).

Section 9 reorganizes a string so no two equal letters sit together. A max-heap by count pops the most frequent letter, holds the previous one back for a step, then pushes it again if it still has count left. O(n log 26). Section 10 builds the nth ugly number, a number whose only prime factors are 2, 3, and 5. A min-heap plus a seen set pops the next ugly number and pushes x*2, x*3, and x*5. O(n log n).

When you talk about it, say this: the root is the winner in O(1), push and pop are O(log n), and top k is a heap of size k at O(n log k).

Everything below is the demonstration. Same idea, written as code you can run.