Binary heap
A heap keeps the smallest value on top without sorting everything. It is a tree stored in an array: index k has children 2k + 1 and 2k + 2. A new value goes in the next free spot at the bottom, then swaps upward while its parent is bigger.
73951826
Push the values into a min-heap one at a time: every parent stays no bigger than its children. Press play to start.
1function push(heap, value) {2 heap.push(value);3 let i = heap.length - 1;4 while (i > 0) {5 const parent = Math.floor((i - 1) / 2);6 if (heap[parent] <= heap[i]) break;7 swap(heap, i, parent);8 i = parent;9 }10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | per push, when the new value is not smaller than its parent |
| average | 1 | per push on random input: most values stay near the bottom |
| worst | log n | per push, when the new value rises to the root |
| space | n | the heap is just the array |
Where it breaks
- Falling input is the worst case. Pick Falling: every new value is the smallest yet, so each one climbs all the way to the root. That is still only log n swaps per push.
- A heap is not sorted. Only the root is guaranteed. Siblings can be in any order, so looking for an arbitrary value is a linear search. Use it when you only ever need the smallest, as a priority queue does.
- Building a heap from a full array. Pushing n values one by one costs up to n log n. Sifting down from the middle of the array, as heapsort does, builds the same kind of heap in n steps.