Heaps and priority queues
A binary heap is a complete binary tree stored in a flat array, maintaining one rule: every parent compares favourably to its children. That single invariant gives O(1) access to the minimum or maximum and O(log n) insertion and removal.
Because the tree is complete, the array layout needs no pointers — children of index i live at 2i+1 and 2i+2. The visualizer shows both views at once so the sift-up and sift-down paths are visible in the tree and in the array.
Time and space complexity
| Operation | Time | Notes |
|---|---|---|
| peek min / max | O(1) | Always the root, index 0 |
| insert | O(log n) | Sift up along one root path |
| extract min / max | O(log n) | Swap root with last, then sift down |
| build heap from array | O(n) | Bottom-up heapify, not O(n log n) |
| search arbitrary value | O(n) | Heaps are only partially ordered |
How to use this visualizer
Choose a min-heap or max-heap track.
Insert a value and follow the sift-up path to its final position.
Extract the root and watch the last element move up then sift down.
Compare the tree diagram against the array indices at every step.
Frequently asked questions
A heap enforces order only between parent and child, so the minimum or maximum is at the root but siblings are unordered — finding an arbitrary value costs O(n). A binary search tree enforces a full left-less-than-node-less-than-right ordering, giving O(log n) search and sorted in-order traversal, but no O(1) access to the extreme value.
Bottom-up heapify sifts down from the last internal node upward. Most nodes sit near the bottom and sift down only a level or two; only the root can travel the full height. Summing the work across all levels gives a geometric series that converges to O(n), even though each individual sift-down is O(log n) in the worst case.
Maintain a min-heap of size k. Push each element, and whenever the heap exceeds k, pop the smallest. Every element costs at most O(log k), so the total is O(n log k) time and O(k) space — considerably better than sorting the whole array when k is small.