Overview
A Binary Max-Heap is a complete binary tree stored compactly in an array, where every parent node is greater than or equal to its children. This ordering keeps the maximum element always at the root, ready to be read in O(1).
Because the tree is complete, a node at index i finds its children at 2i+1 and 2i+2, so no pointers are needed. This array-backed heap is the standard implementation behind priority queues.
How Heap (Binary Max-Heap) works
- Insert appends the new value at the end, then sifts it up: swap with the parent while it is larger.
- Extract-max removes the root, moves the last element to the top, then sifts it down past its larger child.
- Sifting up or down touches at most one node per level, so it costs O(log n).
- Building a heap from an unordered array sifts down from the last parent to the root, costing only O(n).
When to use it
- Implementing priority queues, where the highest-priority item must be served first.
- The engine inside Heap Sort and the frontier of Dijkstra's and A* shortest-path search.
- Streaming problems like finding the top-k largest elements without sorting everything.
Complexity analysis
Insert and extract-max each run in O(log n) because they sift along a single root-to-leaf path. Reading the maximum is O(1). Building a heap from n elements is O(n), not O(n log n), thanks to the sift-down build. Space is O(n).
Frequently asked questions
Why is building a heap O(n) and not O(n log n)?
Most nodes sit near the bottom and sift down only a few levels; summing the work across all levels forms a converging series that totals O(n), not n independent O(log n) inserts.
What is the difference between a heap and a binary search tree?
A heap only guarantees the parent-child order, so it finds the max quickly but cannot search arbitrary values efficiently; a binary search tree keeps a full left-right order for O(log n) lookups.