Binary Heap
A complete tree that keeps one extreme value at the root
Tree shape from array indices
A binary heap is a complete binary tree usually stored in an array. For a node at index i, its children are at 2i + 1 and 2i + 2. No pointers are needed, and the complete shape keeps the height at O(log n).
Restore order along one path
In a max heap, every parent is at least as large as its children. Insertion appends a leaf and sifts it upward. Extracting the maximum moves the final leaf to the root and sifts it downward. Both repairs touch only one root-to-leaf path.
Try it
Array
90
70
80
40
60
30
50
0
1
2
3
4
5
6
Tree view of the same heap
90
70
80
40
60
30
50
Enter a value and insert it to watch it sift up from the array tail.
Costs: peek at the root in
O(1); insert or extract in O(log n); build a heap bottom-up in O(n). Heaps implement priority queues and power Heap Sort. Unlike a binary search tree, they do not keep the entire set in sorted order.