A heap is a tree-shaped structure with one narrow guarantee: every parent is smaller than its children in a min-heap, or larger than its children in a max-heap. It does not promise full ordering the way a binary search tree does — only that the smallest, or largest, element is always at the root, reachable in O(1). That narrow guarantee is exactly what a priority queue needs, which is why a heap sits behind task schedulers, event simulations, and graph algorithms like Dijkstra's.
What changed in 2026
- Heaps stayed conceptually unchanged, but their footprint in AI infrastructure grew. Beam search decoding, top-k retrieval, and priority-based request scheduling in inference servers all lean on heap-based priority queues to keep the k best candidates without sorting everything.
- Pairing heaps and Fibonacci heaps remain mostly academic. In practice, the plain binary heap, array-backed, still wins on real hardware because of cache locality, despite worse theoretical bounds on some operations for the fancier variants.
- Standard libraries continue to expose heaps directly. Python heapq, Java PriorityQueue, and C++ priority_queue are all binary heaps under the hood, so most developers never hand-write one.
The array representation
A binary heap is a complete binary tree, and complete binary trees can be stored in a plain array with no pointers at all, using index arithmetic:
For a node at index i (0-based):
left child = 2*i + 1
right child = 2*i + 2
parent = (i - 1) / 2 (integer division)
This is why a heap is dramatically more cache-friendly than a pointer-based tree like a BST — it is just an array, with structure implied by index math instead of stored pointers.
Core operations
- Peek, find min or max: O(1) — always the root, index 0.
- Insert: append the new value at the end of the array, then bubble it up, swapping it with its parent repeatedly until the heap property holds. O(log n).
- Extract min or max: remove the root, move the last element into its place, then bubble it down, swapping with the smaller or larger child repeatedly until the heap property holds. O(log n).
- Heapify, building from an unsorted array: O(n), not O(n log n) — a common surprise, because most nodes sit near the bottom and need very few swaps.
Heap vs the alternatives
| Structure |
Find min |
Insert |
Extract min |
Sorted iteration |
| Unsorted array |
O(n) |
O(1) |
O(n) |
No |
| Sorted array |
O(1) |
O(n) |
O(1) |
Yes |
| Binary heap |
O(1) |
O(log n) |
O(log n) |
No |
| Binary search tree |
O(log n)* |
O(log n) |
O(log n) |
Yes |
*O(log n) for a balanced BST, following the leftmost node.
Where heaps actually get used
- Priority queues for task schedulers, event-driven simulations, and A* or Dijkstra's algorithm, anywhere the next cheapest thing to process needs to be found repeatedly.
- Heap sort, repeatedly extracting the min or max from a heap built over the whole array — O(n log n) guaranteed, in place, though not stable and usually slower in practice than a well-tuned quicksort.
- Top-k problems, keeping a heap of size k while scanning a much larger stream, giving the k largest or smallest elements in O(n log k) instead of sorting everything.
- Median maintenance, using two heaps, a max-heap for the lower half and a min-heap for the upper half, to give O(log n) insert and O(1) median lookup on a live stream.
Common pitfalls
Expecting a heap to support fast arbitrary search. A heap only guarantees fast access to the min or max. Finding an arbitrary value is O(n), the same as an unsorted array.
Assuming a heap is fully sorted. Only the root is guaranteed correct relative to everything else. Reading the underlying array left to right does not produce sorted order.
Rebuilding the whole heap instead of using a decrease-key style operation. Many implementations need a lower-the-priority-of-an-existing-item operation; removing and reinserting works but is wasteful compared to bubbling the changed node directly.
FAQ
Is a heap the same as a binary search tree?
No. A heap only orders parent versus child; a BST orders an entire subtree relative to a node. A heap cannot efficiently answer a range query between X and Y; a BST can.
Why is building a heap from an array O(n) instead of O(n log n)?
Because heapify starts from the bottom of the tree, where most nodes live, and bottom nodes need at most one or two swaps. The math works out to a linear bound overall, not the naive per-insert bound.
When should a heap be used instead of just sorting the array?
When the min or max is needed repeatedly while the collection keeps changing, rather than a single one-time sort. Sorting once is wasted work if the data changes afterward.
Where to go next