0
Challenge · 57Heaps & Top-K

Heaps from scratch

Heapsused in ~80% of apps

JavaScript has no heap. Python has one, Java has one, C++ has one, and you have an array and about twenty lines. So this tier starts by building the tool, because nobody is going to hand it to you in the round.

Core idea. Keep one flat array where every parent is smaller than both of its children. That is the only rule, and it is much weaker than being sorted, which is exactly why it is cheap to maintain. The smallest value is then always sitting at slot 0.
Playground, this isn't a screenshot
click a slot. The tree is only a way of reading the array
the actual array
1
0
3
1
2
2
5
3
9
4
8
5
4
6
index arithmetic
parent(i) = (i - 1) >> 1
left(i) = 2i + 1
right(i) = 2i + 2
There are no node objects and no pointers here. It is one flat array, and the tree is a picture drawn from the indexes.

No node objects and no pointers. A heap is one flat array, and the tree is drawn from the index arithmetic.

↑ play a little first, then dig in