Recursion and trees · Lesson 18 of 23
Heaps and priority queues
The smallest or largest item in O(1), insert and remove in O(log n), and "top k" problems.
A heap is a complete binary tree stored in an array with one rule: each parent is less than or equal to its children (a min-heap). So the smallest item is always heap[0].
- Peek at the smallest: O(1).
- Insert or remove the smallest: O(log n).
That's exactly a priority queue: a line that serves the most important item first (tasks, Dijkstra, merging k lists).
heap =
Item i has children at 2i + 1 and 2i + 2 and its parent at floor((i - 1) / 2). No pointers: arithmetic is enough.
// JavaScript has no built-in heap, so interviews often ask you to write one
class MinHeap {
constructor() { this.a = [] }
get size() { return this.a.length }
peek() { return this.a[0] }
push(x) {
const a = this.a
a.push(x)
let i = a.length - 1
while (i > 0) { // bubble up while smaller than the parent
const p = (i - 1) >> 1
if (a[p] <= a[i]) break
;[a[p], a[i]] = [a[i], a[p]]
i = p
}
}
pop() {
const a = this.a, top = a[0], last = a.pop()
if (a.length) {
a[0] = last
let i = 0
for (;;) { // sink down to the smaller child
const l = 2 * i + 1, r = l + 1
let m = i
if (l < a.length && a[l] < a[m]) m = l
if (r < a.length && a[r] < a[m]) m = r
if (m === i) break
;[a[m], a[i]] = [a[i], a[m]]
i = m
}
}
return top
}
}
const h = new MinHeap()
for (const x of [5, 3, 8, 1, 9, 2]) h.push(x)
const out = []
while (h.size) out.push(h.pop())
console.log(out.join(" "))Top k: a small heap of size k
Want the largest k of a million items? Don't sort them all (O(n log n)). Keep a min-heap of size k: push each item, and if the size exceeds k, pop the smallest. At the end the heap holds the top k and peek() is the kth largest. Cost: O(n log k).
Quick question
You need the 10 largest numbers from a stream of a billion, with limited memory. The best approach?
Exercise
Use MinHeap (included) to write kthLargest(nums, k) with a heap of size k. It must print 5 4.
Expected output: 5 4
class MinHeap {
constructor() { this.a = [] }
get size() { return this.a.length }
peek() { return this.a[0] }
push(x) { const a = this.a; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (a[p] <= a[i]) break; [a[p], a[i]] = [a[i], a[p]]; i = p } }
pop() { const a = this.a, top = a[0], last = a.pop(); if (a.length) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && a[l] < a[m]) m = l; if (r < a.length && a[r] < a[m]) m = r; if (m === i) break; [a[m], a[i]] = [a[i], a[m]]; i = m } } return top }
}
function kthLargest(nums, k) {
}
console.log(kthLargest([3, 2, 1, 5, 6, 4], 2), kthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.