Heap
A tree-shaped priority queue that keeps the min or max element accessible in O(1).
- 1 Lesson
Dry-run engine
Min-Heap Push (Sift-Up)
A heap is a tree with no pointers — index arithmetic over a flat array does all the linking.
- Input
- heap = [2, 4, 3, 7, 9, 5, 8], push(1)
- Output · Heap array
- Press play to run it
How it works
Write the new value at the end of the array, then sift up: while it is smaller than its parent at (i - 1) / 2, swap the two.
heap_array[8] · implicit tree
- i—
- parent—
- Compare—
- Size7
The tree is only a way of looking at it: the heap is the flat array below. Node i keeps its children at 2i + 1 and 2i + 2 and its parent at (i - 1) / 2 — no pointers are stored at all.
1 / 5
Course Contents
Related courses
- ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
- StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
- Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems