Lessons · TypeScript · heaps (the smallest first)
Always hand me the smallest
A heap keeps only enough order to know its minimum, so push and pop each cost about log n. JavaScript has no heap in the standard library, so you write the two loops yourself.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
When you need the best few out of an enormous number of things, sorting everything is wasted work. A heap of size k gives the top k for n log k and never holds the whole stream.
How to think about it
Say 'smallest so far' or 'best k' and reach for a heap. Push bubbles a value up toward the root; pop moves the last value to the root and sinks it. For the k largest, keep a min-heap of size k.
Worked example
const h = [];The heap is a plain array: children of i are 2i+1 and 2i+2.
function push(v) {h.push(v);In at the end.
let i = h.length - 1;
while (i > 0 && h[(i - 1) >> 1] > h[i]) {While the parent is bigger, swap upward.const p = (i - 1) >> 1;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
}
for (const v of [5, 1, 9, 3]) push(v);
console.log(h[0]);1
console.log([...h].sort((a, b) => a - b).join(','));1,3,5,9Your turn
Find the parent of the node at index i.
const parent = (i - 1) >> ;
Solve one with the tests running
The trap
h[0] is the smallest and the rest is NOT sorted. Printing a heap shows a jumble, and that is correct: partial order is what makes it cheap.