Heaps & Priority Queues
Beginner · 14 min read · Data Structures Basics, Trees, Heaps & Graphs
A complete tree stored in an array: always know the minimum, in O(log n) per change.
Many problems need the smallest (or largest) item, again and again, while new items keep arriving: the next task by priority, the closest point so far, the k largest values in a stream.
A heap gives you the minimum in O(1) and handles each insert or removal in O(log n). Java calls it a PriorityQueue.
Picture it
How it works
A (binary) min-heap is a complete binary tree with one rule: every parent is ≤ its children. So the root is the minimum. Nothing else is ordered: siblings can be in any order, and the heap is not sorted.
Types
Operations and their cost
A heap is the best balance when inserts and removals of the minimum are interleaved.
In Java
Patterns that use heaps
Interview questions
- Why is a heap stored in an array instead of with node objects?
- Why does building a heap with heapify take O(n) rather than O(n log n)?
Further reading
Key takeaways
- A min-heap is a complete tree where every parent is ≤ its children, so the minimum sits at the root.
- It's stored in an array: children of i at 2i + 1 and 2i + 2, parent at (i − 1) / 2.
- offer sifts up and poll moves the last element to the root and sifts down: O(log n). Peek is O(1).
- Heapify builds a heap in O(n). A heap is not sorted, and arbitrary search is O(n).
- In Java use PriorityQueue, with Comparator.reverseOrder() for a max-heap and Integer.compare in comparators.