← Data structures from scratch · Lesson 22/32
A tree stored in an array
The smallest, always on top
A min-heap is a binary tree with two rules:
- Every parent is less than or equal to its children. So the root is the minimum of everything.
- It's complete: it fills level by level, left to right, with no gaps.
It isn't fully sorted: there's no rule between siblings or cousins. It promises only one thing, that the smallest is on top, and that's exactly what makes it cheap.
Since it has no gaps, it needs no nodes or pointers: it's stored in an array, level by level. The children of position i are at 2i + 1 and 2i + 2, and its parent at (i - 1) >> 1 (divide by 2 and drop the decimals).
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
- Every parent is smaller than both children: 1 → 3 and 2; 3 → 7 and 4; 2 → 5 and 8.
- Position 5 (the 5) has position 2 (the 2) as its parent.
- The minimum is at
heap[0]: reading it costs O(1).
The whole lesson on one page
The smallest, always on top
A min-heap is a binary tree with two rules:
- Every parent is less than or equal to its children. So the root is the minimum of everything.
- It's complete: it fills level by level, left to right, with no gaps.
It isn't fully sorted: there's no rule between siblings or cousins. It promises only one thing, that the smallest is on top, and that's exactly what makes it cheap.
Since it has no gaps, it needs no nodes or pointers: it's stored in an array, level by level. The children of position i are at 2i + 1 and 2i + 2, and its parent at (i - 1) >> 1 (divide by 2 and drop the decimals).
// The tree in the drawing, stored level by level
const heap = [1, 3, 2, 7, 4, 5, 8];
for (let i = 0; i < heap.length; i++) {
const izq = 2 * i + 1, der = 2 * i + 2;
if (izq < heap.length) {
console.log("position", i, "value", heap[i], "-> children", heap[izq], heap[der]);
}
}
console.log("the parent of position 5 is", heap[(5 - 1) >> 1]);
console.log("the minimum:", heap[0]);
- Every parent is smaller than both children: 1 → 3 and 2; 3 → 7 and 4; 2 → 5 and 8.
- Position 5 (the 5) has position 2 (the 2) as its parent.
- The minimum is at
heap[0]: reading it costs O(1).
Pushing: at the end, then up
To push a value without breaking the shape, it goes at the end of the array (the next slot on the last level). Then it moves up: while it's smaller than its parent, they swap.
Since the tree is complete, its height is log₂ n, and moving up takes at most that many steps: O(log n). Watch the array after each value.
function subir(heap, i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
}
function meter(heap, valor) {
heap.push(valor);
subir(heap, heap.length - 1);
}
const heap = [];
for (const v of [5, 3, 8, 1, 9, 2]) {
meter(heap, v);
console.log(v, "->", heap);
}
- The 1 enters at the end,
[3, 5, 8, 1], and moves up twice: past 5 and then past 3, until it's the root. - The 9 doesn't move at all: it's already bigger than its parent.
- The 2 moves up once and stays under the 1. The final array isn't sorted, but the minimum is at position 0.
Popping the minimum: last one on top, then down
The minimum is the root. To remove it without leaving a gap, the last element moves to the root and moves down: it swaps with the smaller of its two children while either one is smaller than it. Also O(log n).
If you pop the minimum over and over, the values come out in order: that's heapsort, sorting in O(n log n) with no extra memory.
function bajar(heap, i) {
const n = heap.length;
while (true) {
const izq = 2 * i + 1, der = 2 * i + 2;
let menor = i;
if (izq < n && heap[izq] < heap[menor]) menor = izq;
if (der < n && heap[der] < heap[menor]) menor = der;
if (menor === i) break;
[heap[menor], heap[i]] = [heap[i], heap[menor]];
i = menor;
}
}
function sacar(heap) {
const min = heap[0];
const ultimo = heap.pop();
if (heap.length > 0) {
heap[0] = ultimo;
bajar(heap, 0);
}
return min;
}
const heap = [1, 3, 2, 5, 9, 8];
console.log(sacar(heap), heap);
const salen = [];
while (heap.length > 0) salen.push(sacar(heap));
console.log(salen);
- Popping 1 moves 8 (the last one) to the root and it sinks to its place:
[2, 3, 8, 5, 9]. - Popping everything gives
[2, 3, 5, 8, 9]: sorted. - The
ifhandles the single-element case: without it, the last item would come back right after being removed.