A priority queue answers one question quickly: which item is the most urgent right now? A heap is the standard structure behind it.
Shape and rule
A binary heap is a complete binary tree stored in an array. In a min-heap, every parent is no larger than its children, so the smallest item sits at the root. For the node at index i, the children are at 2*i* + 1 and 2*i* + 2, and the parent is at (i − 1) // 2. No pointers are needed.
Two operations do the work
To insert, place the new item at the end and move it up while it is smaller than its parent. To remove the minimum, take the root, move the last item into its place, and move it down by swapping with its smaller child until the rule holds again. Each operation travels at most the height of the tree, so both are O(log n). Reading the minimum is O(1).
Where heaps appear
- Dijkstra's shortest-path algorithm and A* use a priority queue to pick the next node.
- Schedulers use one to run the highest-priority task first.
- "Top k" problems keep a heap of size k.
- Heapsort uses a heap to sort in O(n log n).
A heap is not a sorted list
A heap guarantees only that the root is the minimum. The rest of the array is only partially ordered. To read all items in order you must remove them one at a time. Building a heap from n existing items is possible in O(n).
A handy trick
To find the k largest values in a stream, keep a min-heap of size k. When a new value beats the smallest value in the heap, swap it in. The heap always holds the best k seen so far.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithms Made Simple.
Adapted from Algorithms Made Simple, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.