Heaps and Priority Queues
Heaps and Priority Queues
JavaScript has no heap. You will have to write one, and it is the single most useful structure you can carry into an interview - it turns every 'top k' question from a sort into a scan.
What a heap guarantees
A min-heap keeps the smallest element at the root. Not a sorted list - just the guarantee that every parent is smaller than its children. That weaker promise is what makes it cheap to maintain.
- Peek the smallest - O(1).
- Insert - O(log n).
- Remove the smallest - O(log n).
- Build from n items - O(n).
Stored as a flat array
A heap is a complete binary tree, so it needs no node objects. Positions are arithmetic:
The index maths
javascript
// For the element at index i:
const parent = (i) => Math.floor((i - 1) / 2)
const left = (i) => 2 * i + 1
const right = (i) => 2 * i + 2
// 1 index 0
// / \
// 3 5 index 1, 2
// / \
// 4 8 index 3, 4
// stored as: [1, 3, 5, 4, 8]A working min-heap
MinHeap
javascript
class MinHeap {
#items = []
get size() { return this.#items.length }
peek() { return this.#items[0] }
push(value) {
this.#items.push(value)
this.#bubbleUp(this.#items.length - 1)
}
pop() {
if (this.#items.length === 0) return undefined
const top = this.#items[0]
const last = this.#items.pop()
if (this.#items.length > 0) {
this.#items[0] = last
this.#bubbleDown(0)
}
return top
}
#bubbleUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2)
if (this.#items[parent] <= this.#items[i]) break
this.#swap(parent, i)
i = parent
}
}
#bubbleDown(i) {
const n = this.#items.length
while (true) {
const left = 2 * i + 1
const right = 2 * i + 2
let smallest = i
if (left < n && this.#items[left] < this.#items[smallest]) smallest = left
if (right < n && this.#items[right] < this.#items[smallest]) smallest = right
if (smallest === i) break
this.#swap(i, smallest)
i = smallest
}
}
#swap(a, b) {
;[this.#items[a], this.#items[b]] = [this.#items[b], this.#items[a]]
}
}
const heap = new MinHeap()
for (const n of [5, 3, 8, 1]) heap.push(n)
console.log(heap.pop(), heap.pop()) // 1 3A max-heap, without rewriting it
Push negated values into a min-heap and negate on the way out. For objects, pass a comparator instead.
Priority queue with a comparator
javascript
// A comparator-driven heap, complete and runnable on its own.
class PriorityQueue {
#items = []
#compare
constructor(compare = (a, b) => a - b) { this.#compare = compare }
get size() { return this.#items.length }
peek() { return this.#items[0] }
push(value) {
this.#items.push(value)
let i = this.#items.length - 1
while (i > 0) {
const parent = Math.floor((i - 1) / 2)
if (this.#compare(this.#items[parent], this.#items[i]) <= 0) break
;[this.#items[parent], this.#items[i]] = [this.#items[i], this.#items[parent]]
i = parent
}
}
pop() {
if (this.#items.length === 0) return undefined
const top = this.#items[0]
const last = this.#items.pop()
if (this.#items.length) {
this.#items[0] = last
let i = 0
while (true) {
const l = 2 * i + 1
const r = 2 * i + 2
let best = i
if (l < this.#items.length && this.#compare(this.#items[l], this.#items[best]) < 0) best = l
if (r < this.#items.length && this.#compare(this.#items[r], this.#items[best]) < 0) best = r
if (best === i) break
;[this.#items[i], this.#items[best]] = [this.#items[best], this.#items[i]]
i = best
}
}
return top
}
}
// Highest priority first.
const queue = new PriorityQueue((a, b) => b.priority - a.priority)
queue.push({ task: "low", priority: 1 })
queue.push({ task: "urgent", priority: 9 })
console.log(queue.pop()) // { task: "urgent", priority: 9 }Where it earns its place
Anywhere you repeatedly need the current best without sorting everything: task schedulers, Dijkstra's algorithm, merging sorted streams, and every top-k question.