Heaps and Priority Queues

Table of Contents

1. Who Goes Next?
2. The Priority Queue Idea
3. Why Not Just Sort?
4. The Binary Heap
5. A Tree Inside an Array
6. Push and Sift Up
7. Pop and Sift Down
8. Building PriorityQueue
9. Heap Sort and Top-K
10. Real Problems: Scheduler, Median, Merge
11. Recipe: priority-queue.ts for algolab
12. Try It Yourself

1. Who Goes Next?

A regular queue serves people in the order they arrived. That is fair, but sometimes it is the wrong rule:

• A hospital sees a patient with a broken leg before someone with a sore throat, even if the sore throat arrived first.
• A payment server should charge a card before it resizes a profile picture.
• A map app wants the road with the lowest total cost next, not the one it found first.
• An operating system gives urgent processes the CPU before background ones.

In each case, items wait in a line but the next one out is chosen by priority, not by arrival time. The structure for this is the priority queue, and the clever way to build one is the binary heap. It is the engine behind task schedulers, "top 10" lists, event simulations, and the shortest-path algorithm (Dijkstra) you will meet in the next chapter.

2. The Priority Queue Idea

A priority queue is an abstract data type: it says what you can do, not how it is built. It has these operations:

In this chapter "highest priority" means "sorts first". That makes it a min-priority queue: the smallest value comes out first, so a task with priority 1 beats one with priority 5. To get a max version, flip the comparison (we will do that with a comparator, just like Array.sort).

JavaScript has no built-in priority queue. That surprises people, since it has Array, Map, and Set. Many other languages do ship one (Java's PriorityQueue, Python's heapq, C++'s priority_queue), and in interviews you are normally expected to either say "I would use a heap here" or write a small one yourself. So we will.

3. Why Not Just Sort?

Two simple ideas come to mind first. Both are slower than they need to be.

Idea A: keep an unsorted array. push is O(1), but pop must scan every item to find the smallest, which is O(n).

Idea B: keep a sorted array. pop is O(1) if the smallest is at the end, but every push must find its place and shift items over, so it is O(n) (remember, from the Arrays and Strings chapter, that inserting in the middle of an array moves everything after it).

Either way, one of the two operations costs O(n). If you do n pushes and n pops, the total is O(n²). For 100,000 tasks, that is ten billion steps. The heap gets both operations down to O(log n):

For 100,000 items, log₂ n is about 17. The heap does about 17 steps per operation where the array does tens of thousands. If you need a refresher on why log n is so small, see the Big-O chapter of Math for Programmers.

4. The Binary Heap

A binary heap is a binary tree (each node has at most two children, as in the previous chapter) with two rules:

1. Shape rule: the tree is complete. Every level is full except possibly the last one, and the last level is filled from left to right with no gaps.
2. Heap rule (for a min-heap): every node is less than or equal to its children.

          1
        /   \
       3     2
      / \   /
     5   9 8

Check the heap rule: 1 <= 3 and 1 <= 2. Then 3 <= 5 and 3 <= 9. Then 2 <= 8. It holds everywhere. The smallest value is always at the root, so peek() is just "look at the top".

Be careful not to confuse this with the binary search tree from the last chapter. A BST orders left versus right: left is smaller, right is larger. A heap orders parent versus child: the parent is smaller than both children, and left and right have no order between them (in the picture, 3 is on the left of 2, and that is fine). The heap is much less strict, and that is exactly why it is cheaper to keep valid. It only promises one thing: the smallest item is on top.

The shape rule gives us a gift: because the tree is always complete, its height is always about log₂ n. A heap can never degrade into a long skinny line like an unbalanced BST. The price is that you cannot search inside it. A heap is good at exactly one thing, and it does it well: "give me the smallest next".

5. A Tree Inside an Array

Because the tree is complete (no gaps), we do not need node objects and pointers at all. We can store it in a plain array, reading the tree row by row from left to right:

tree:       1               array:  index:  0  1  2  3  4  5
          /   \                     value: [1, 3, 2, 5, 9, 8]
         3     2
        / \   /
       5   9 8

The family relationships become simple arithmetic on the index i:

Check it with the array above. Index 1 (value 3) has children at 2*1+1 = 3 (value 5) and 2*1+2 = 4 (value 9). Right. The parent of index 5 (value 8) is Math.floor((5-1)/2) = 2 (value 2). Right again.

This is a neat trick. No nodes, no left/right fields, no pointers, and the data is packed together in memory, which is friendly to the CPU cache (the same reason arrays beat linked lists in practice). It is also a nice callback to the modular arithmetic idea that numbers can be used as addresses.

6. Push and Sift Up

To add a value, we must keep both rules true. The shape rule says the new item must go in the next free spot, which is simply the end of the array. That may break the heap rule, if the new item is smaller than its parent. So we fix it by sifting up: while the item is smaller than its parent, swap them.

Let's push 5, 3, 8, 1, 9, 2 one at a time into an empty heap:

push 5:   [5]
push 3:   [5, 3]           3 < parent 5, swap          -> [3, 5]
push 8:   [3, 5, 8]        8 >= parent 3, stay
push 1:   [3, 5, 8, 1]     1 < parent 5, swap          -> [3, 1, 8, 5]
                           1 < parent 3, swap          -> [1, 3, 8, 5]
push 9:   [1, 3, 8, 5, 9]  9 >= parent 3, stay
push 2:   [1, 3, 8, 5, 9, 2]  2 < parent 8, swap       -> [1, 3, 2, 5, 9, 8]
                           2 >= parent 1, stop

The final array [1, 3, 2, 5, 9, 8] is exactly the heap from the picture in section 4.

Here is the sift up step in code:

function siftUp(items: number[], index: number): void {
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);
    if (items[index] >= items[parent]) break; // heap rule holds: stop
    [items[index], items[parent]] = [items[parent], items[index]];
    index = parent;
  }
}

The item can climb at most from the bottom to the root, which is the height of the tree, about log₂ n levels. That is why push is O(log n).

7. Pop and Sift Down

pop removes the root, which leaves a hole at the top. The trick is to avoid shifting the whole array:

1. Save the root (the answer).
2. Take the last item in the array and move it to the root. This keeps the shape complete.
3. That item is probably too big for the top. Sift down: compare it with its two children, swap it with the smaller child, and repeat until it is no bigger than both children, or it has none.

Pop from [1, 3, 2, 5, 9, 8]:

answer = 1
move last item (8) to the root:  [8, 3, 2, 5, 9]
children of 8 are 3 and 2. Smaller is 2, swap:  [2, 3, 8, 5, 9]
8 is now at index 2. Children at 5 and 6 do not exist. Stop.

The heap is now [2, 3, 8, 5, 9]. The next pop will return 2, and so on, giving 1, 2, 3, 5, 8, 9 in order.

Why swap with the smaller child? Because that child becomes the new parent of the other one, so it must be no bigger than it. If we swapped with the larger child, the smaller one would end up below it and break the heap rule.

function siftDown(items: number[], index: number): void {
  const n = items.length;
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

    if (left < n && items[left] < items[smallest]) smallest = left;
    if (right < n && items[right] < items[smallest]) smallest = right;

    if (smallest === index) break; // heap rule holds: stop
    [items[index], items[smallest]] = [items[smallest], items[index]];
    index = smallest;
  }
}

Again at most one trip from top to bottom, so pop is O(log n). The checks left < n and right < n matter: they stop us reading past the end of the array.

8. Building PriorityQueue

Now we wrap this in a class. We take an optional compare function so the same code can handle numbers, strings, and objects, and so you can flip the order for a max-heap. The comparison convention is the same as Array.sort: a negative number means "a goes first".

type Compare<T> = (a: T, b: T) => number;

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

class PriorityQueue<T> {
  private items: T[] = [];

  constructor(private compare: Compare<T> = defaultCompare) {}

  get size(): number {
    return this.items.length;
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  peek(): T | undefined {
    return this.items[0];
  }

  push(item: T): void {
    this.items.push(item);
    this.siftUp(this.items.length - 1);
  }

  pop(): T | undefined {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];
    const last = this.items.pop() as T;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  // siftUp, siftDown and swap go here (see the recipe)
}

Notice the order inside pop. We remove the last item first with this.items.pop(). If the heap had only one item, the last item is the top, and the array is now empty, so we must not put it back. That is why the if (this.items.length > 0) check exists. Forgetting it is a classic bug that leaves a ghost item behind.

Using it:

const pq = new PriorityQueue<number>();
for (const n of [5, 3, 8, 1, 9, 2]) pq.push(n);

console.log(pq.peek()); // 1
console.log(pq.size);   // 6

const out: number[] = [];
while (!pq.isEmpty()) out.push(pq.pop() as number);
console.log(out.join(" ")); // 1 2 3 5 8 9

Popping everything gives sorted output. Did you notice what we just did? That is a sorting algorithm.

For objects, pass a comparator that says which field decides:

interface Job {
  name: string;
  priority: number;
}

const jobs = new PriorityQueue<Job>((a, b) => a.priority - b.priority);
jobs.push({ name: "send newsletter", priority: 3 });
jobs.push({ name: "charge card", priority: 1 });
jobs.push({ name: "resize image", priority: 2 });

console.log(jobs.pop()?.name); // charge card

And for a max-heap, swap the arguments so bigger numbers sort first:

const biggestFirst = new PriorityQueue<number>((a, b) => b - a);
for (const n of [5, 3, 8]) biggestFirst.push(n);

console.log(biggestFirst.pop()); // 8

9. Heap Sort and Top-K

Heap sort. Push every value into a heap, then pop them all. Each push and pop costs O(log n), and we do n of each, so the whole sort is O(n log n), the same as merge sort from the Sorting chapter:

function heapSort<T>(
  values: T[],
  compare: Compare<T> = defaultCompare,
): T[] {
  const heap = new PriorityQueue(compare);
  for (const v of values) heap.push(v);

  const sorted: T[] = [];
  while (!heap.isEmpty()) sorted.push(heap.pop() as T);
  return sorted;
}

console.log(heapSort([5, 3, 8, 1, 9, 2]));
// [ 1, 2, 3, 5, 8, 9 ]
console.log(heapSort(["pear", "apple", "fig"]));
// [ 'apple', 'fig', 'pear' ]

This version uses O(n) extra memory for the heap. The textbook version sorts in place by turning the input array itself into a heap, then repeatedly swapping the top with the last unsorted item. It needs no extra array, but it is not stable, and in practice quicksort and merge sort are usually faster because they are friendlier to the CPU cache. Heap sort's real value is its guaranteed O(n log n) worst case, and the idea behind it, which powers the next trick.

Top-K. A very common question: "from a stream of a million scores, give me the top 10". The obvious way is to sort everything and take the first 10. That costs O(n log n), and it also needs all the data in memory.

The heap does better. Keep a min-heap of size K. For every new value, push it, and if the heap now has more than K items, pop the smallest. Whatever is left in the heap at the end is the K largest values. (It feels backwards to use a min-heap to find the largest, but the smallest of the current best K is the one that is first to be kicked out, and that is exactly what a min-heap hands you.)

function topK(values: number[], k: number): number[] {
  const heap = new PriorityQueue<number>();
  for (const v of values) {
    heap.push(v);
    if (heap.size > k) heap.pop(); // drop the smallest of the k + 1
  }

  const result: number[] = [];
  while (!heap.isEmpty()) result.push(heap.pop() as number);
  return result.reverse(); // biggest first
}

console.log(topK([4, 9, 1, 7, 3, 8, 2], 3));
// [ 9, 8, 7 ]

The heap never holds more than K + 1 items, so each operation costs O(log K), and the whole job is O(n log K) time and O(K) memory. When K is 10 and n is a million, log K is about 3, versus about 20 for a full sort, and you never need to hold a million values at once. This is how "trending now" lists, leaderboards, and "10 largest files in this folder" tools work.

Note one more fact about heaps: building a heap from n values that you already have can be done in O(n) (not O(n log n)) with a clever bottom-up method called "heapify", which sifts down starting from the middle of the array. The simple push-one-by-one loop we use in this chapter is O(n log n), which is fine for almost everything.

10. Real Problems: Scheduler, Median, Merge

A task scheduler. Background jobs arrive with a priority. A worker repeatedly takes the most urgent one. There is one detail to handle: jobs with the same priority should run in the order they arrived. A heap does not promise that by itself (it is not stable), so we add an arrival counter as a tiebreaker:

interface Task {
  name: string;
  priority: number;
  order: number;
}

const tasks = new PriorityQueue<Task>(
  (a, b) => a.priority - b.priority || a.order - b.order,
);

let counter = 0;
const add = (name: string, priority: number) =>
  tasks.push({ name, priority, order: counter++ });

add("send newsletter", 3);
add("charge card", 1);
add("resize image", 2);
add("send receipt", 1);
add("clean logs", 5);

const runOrder: string[] = [];
while (!tasks.isEmpty()) runOrder.push((tasks.pop() as Task).name);

console.log(runOrder);
// [ 'charge card', 'send receipt', 'resize image', 'send newsletter', 'clean logs' ]

The expression a.priority - b.priority || a.order - b.order means "compare by priority, and if that gives 0, compare by arrival order". Both priority-1 tasks come first, and charge card beats send receipt because it was added earlier.

Real job queues (Sidekiq, BullMQ, cloud task services) are built on the same idea, with the data kept in Redis or a database instead of memory.

Kth largest in a stream. Numbers keep arriving, and after each one you must report the k-th largest so far. It is the top-K trick again: the heap of size k has the answer on top, since the smallest of the k largest is the k-th largest:

class KthLargest {
  private heap = new PriorityQueue<number>();

  constructor(private k: number, nums: number[]) {
    for (const n of nums) this.add(n);
  }

  add(value: number): number {
    this.heap.push(value);
    if (this.heap.size > this.k) this.heap.pop();
    return this.heap.peek() as number;
  }
}

const third = new KthLargest(3, [4, 5, 8, 2]);
console.log(third.add(3));  // 4
console.log(third.add(5));  // 5
console.log(third.add(10)); // 5
console.log(third.add(9));  // 8
console.log(third.add(4));  // 8

Trace the first line. After the constructor, the three largest of 4, 5, 8, 2 are 4, 5, 8, so the heap holds those. Adding 3 makes four items, and the smallest (3) is popped, so the answer stays 4.

Merge K sorted lists. You have several already-sorted lists, say three sorted log files from three servers, and want one combined sorted list. Checking the front of every list each time works, but costs O(k) per item. A heap of the current front item of each list gives the smallest in O(log k):

function mergeSorted(lists: number[][]): number[] {
  const heap = new PriorityQueue<{ value: number; list: number; index: number }>(
    (a, b) => a.value - b.value,
  );

  lists.forEach((l, i) => {
    if (l.length > 0) heap.push({ value: l[0], list: i, index: 0 });
  });

  const out: number[] = [];
  while (!heap.isEmpty()) {
    const { value, list, index } = heap.pop()!;
    out.push(value);
    const next = index + 1;
    if (next < lists[list].length) {
      heap.push({ value: lists[list][next], list, index: next });
    }
  }
  return out;
}

console.log(mergeSorted([[1, 4, 7], [2, 5], [3, 6, 9]]));
// [ 1, 2, 3, 4, 5, 6, 7, 9 ]

Each popped item remembers which list it came from, so we know which list to take the next item from. The total cost is O(n log k) for n items in k lists. This is the "merge" step of external sorting, used when data is too large to fit in memory.

Running median. After each new number, report the median (the middle value) of everything seen so far. Sorting each time is too slow. The elegant answer uses two heaps: a max-heap for the smaller half of the numbers and a min-heap for the larger half. The median is then on top of one heap, or the average of both tops:

class RunningMedian {
  private low = new PriorityQueue<number>((a, b) => b - a); // max-heap
  private high = new PriorityQueue<number>();               // min-heap

  add(value: number): void {
    if (this.low.isEmpty() || value <= (this.low.peek() as number)) {
      this.low.push(value);
    } else {
      this.high.push(value);
    }
    // Keep the sizes equal, or `low` one bigger.
    if (this.low.size > this.high.size + 1) {
      this.high.push(this.low.pop() as number);
    } else if (this.high.size > this.low.size) {
      this.low.push(this.high.pop() as number);
    }
  }

  median(): number {
    if (this.low.size > this.high.size) return this.low.peek() as number;
    return ((this.low.peek() as number) + (this.high.peek() as number)) / 2;
  }
}

const rm = new RunningMedian();
const medians: number[] = [];
for (const n of [5, 2, 8, 1, 9, 3]) {
  rm.add(n);
  medians.push(rm.median());
}
console.log(medians);
// [ 5, 3.5, 5, 3.5, 5, 4 ]

Check the last value: the numbers are 1, 2, 3, 5, 8, 9. The middle two are 3 and 5, and the average is 4. Each add is O(log n), and median is O(1).

11. Recipe: priority-queue.ts for algolab

Create src/priority-queue.ts in algolab:

export type Compare<T> = (a: T, b: T) => number;

// A binary heap stored in a plain array. The item that sorts FIRST
// according to `compare` (the smallest) is always at index 0.
export class PriorityQueue<T> {
  private items: T[] = [];

  constructor(private compare: Compare<T> = defaultCompare) {}

  get size(): number {
    return this.items.length;
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  peek(): T | undefined {
    return this.items[0];
  }

  push(item: T): void {
    this.items.push(item);
    this.siftUp(this.items.length - 1);
  }

  pop(): T | undefined {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];
    const last = this.items.pop() as T;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  private siftUp(index: number): void {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.compare(this.items[index], this.items[parent]) >= 0) break;
      this.swap(index, parent);
      index = parent;
    }
  }

  private siftDown(index: number): void {
    const n = this.items.length;
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      let smallest = index;
      if (left < n && this.compare(this.items[left], this.items[smallest]) < 0) {
        smallest = left;
      }
      if (right < n && this.compare(this.items[right], this.items[smallest]) < 0) {
        smallest = right;
      }
      if (smallest === index) break;
      this.swap(index, smallest);
      index = smallest;
    }
  }

  private swap(i: number, j: number): void {
    [this.items[i], this.items[j]] = [this.items[j], this.items[i]];
  }
}

function defaultCompare<T>(a: T, b: T): number {
  return a < b ? -1 : a > b ? 1 : 0;
}

export function heapSort<T>(
  values: T[],
  compare: Compare<T> = defaultCompare,
): T[] {
  const heap = new PriorityQueue(compare);
  for (const v of values) heap.push(v);
  const sorted: T[] = [];
  while (!heap.isEmpty()) sorted.push(heap.pop() as T);
  return sorted;
}

// The k largest values, biggest first. Keeps a min-heap of size k.
export function topK(values: number[], k: number): number[] {
  const heap = new PriorityQueue<number>();
  for (const v of values) {
    heap.push(v);
    if (heap.size > k) heap.pop();
  }
  const result: number[] = [];
  while (!heap.isEmpty()) result.push(heap.pop() as number);
  return result.reverse();
}

Create the tests in src/priority-queue.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import { PriorityQueue, heapSort, topK } from "./priority-queue.ts";

test("pop returns items smallest first", () => {
  const pq = new PriorityQueue<number>();
  for (const n of [5, 3, 8, 1, 9, 2]) pq.push(n);
  assert.equal(pq.peek(), 1);
  const out: number[] = [];
  while (!pq.isEmpty()) out.push(pq.pop() as number);
  assert.deepEqual(out, [1, 2, 3, 5, 8, 9]);
});

test("empty queue returns undefined", () => {
  const pq = new PriorityQueue<number>();
  assert.equal(pq.pop(), undefined);
  assert.equal(pq.peek(), undefined);
  assert.equal(pq.size, 0);
});

test("a comparator turns it into a max-heap", () => {
  const pq = new PriorityQueue<number>((a, b) => b - a);
  for (const n of [5, 3, 8]) pq.push(n);
  assert.equal(pq.pop(), 8);
});

test("works with objects and a priority field", () => {
  const pq = new PriorityQueue<{ name: string; priority: number }>(
    (a, b) => a.priority - b.priority,
  );
  pq.push({ name: "email", priority: 3 });
  pq.push({ name: "payment", priority: 1 });
  pq.push({ name: "report", priority: 2 });
  assert.equal(pq.pop()?.name, "payment");
  assert.equal(pq.pop()?.name, "report");
});

test("heapSort matches Array.sort on random data", () => {
  const data = Array.from({ length: 200 }, () =>
    Math.floor(Math.random() * 1000),
  );
  assert.deepEqual(heapSort(data), [...data].sort((a, b) => a - b));
});

test("topK returns the k largest, biggest first", () => {
  assert.deepEqual(topK([4, 9, 1, 7, 3, 8, 2], 3), [9, 8, 7]);
  assert.deepEqual(topK([1, 2], 5), [2, 1]);
});

The heapSort test is a good habit: compare your algorithm against the trusted built-in on random data, which catches mistakes in siftUp and siftDown that hand-picked examples might miss. Run the tests:

npx tsx --test

Add the export to src/index.ts:

export * from "./priority-queue.ts";

Then create demo-heap.ts in the project root:

import { PriorityQueue, heapSort, topK } from "./src/priority-queue.ts";

const pq = new PriorityQueue<number>();
for (const n of [5, 3, 8, 1, 9, 2]) pq.push(n);
console.log("peek:", pq.peek(), "size:", pq.size);

const out: number[] = [];
while (!pq.isEmpty()) out.push(pq.pop() as number);
console.log("popped:", out.join(" "));

console.log("heapSort:", heapSort([5, 3, 8, 1, 9, 2]).join(" "));
console.log("top 3:", topK([4, 9, 1, 7, 3, 8, 2], 3).join(" "));

const jobs = new PriorityQueue<{ name: string; priority: number }>(
  (a, b) => a.priority - b.priority,
);
jobs.push({ name: "send newsletter", priority: 3 });
jobs.push({ name: "charge card", priority: 1 });
jobs.push({ name: "resize image", priority: 2 });
console.log("next job:", jobs.pop()?.name);

Run it:

npx tsx demo-heap.ts

peek: 1 size: 6
popped: 1 2 3 5 8 9
heapSort: 1 2 3 5 8 9
top 3: 9 8 7
next job: charge card

You will use PriorityQueue again in the next chapter, where it is the engine of Dijkstra's shortest-path algorithm.

12. Try It Yourself

1. Trace it by hand. Push 7, 4, 9, 2, 6 into an empty min-heap and write the array after each push. Then pop once and write the array again. Check your answers by logging the heap in code (you may need to temporarily expose items).
2. Max-heap. Using only the PriorityQueue class, create a structure that always returns the largest string by length. (Hint: the comparator.)
3. Kth smallest. Write kthSmallest(values, k). Which kind of heap do you keep, and of what size? Compare with topK.
4. Closest to zero. Given an array of numbers, return the 3 numbers closest to 0. Use a heap with a comparator that looks at Math.abs. Does the order you pop in depend on how you wrote the comparator?
5. Interview: top K frequent words. Given an array of words and a number k, return the k most frequent words, most frequent first, with ties broken alphabetically. Count with a Map (see Hash Maps and Sets), then use a heap of size k. What is the complexity, and how does it compare with sorting all the distinct words?
6. Interview: connect the ropes. You have ropes of various lengths. Joining two ropes costs the sum of their lengths. Find the cheapest total cost to join them all into one. For [4, 3, 2, 6] the answer is 29. Hint: always join the two shortest. What does that tell you to use?
7. Update a priority. Our heap has no way to change an item's priority after it is pushed. How could you do it with what we have? (One common trick: push a new copy, and skip stale copies when they come out. You will see this exact trick in Dijkstra's algorithm in the next chapter.)

A priority queue is a line where the most important item is always at the front, and a heap makes it cheap. With trees and heaps in hand you are ready for the most general structure of all: items connected in any way you like. In Graphs we model maps, networks, and dependencies, search through them with BFS and DFS, and use your new PriorityQueue to find the cheapest route.