Heaps — Finding the Min or Max in O(1)
heapsdata-structuresintermediatefree
How heaps maintain the smallest (or largest) element at the top — priority queues, heapify, and heap sort.
What Is a Heap?
A heap is a complete binary tree where every parent node satisfies the heap property: in a min heap, every parent is smaller than or equal to its children. In a max heap, every parent is larger.
The result: the minimum (or maximum) element is always at the root. You can read it in O(1). Insert and extract operations are O(log n).
Python’s heapq module implements a min heap. Java’s PriorityQueue is a heap. C++’s priority_queue is a max heap. They power Dijkstra’s algorithm, scheduling systems, and the "top K" pattern.
python
import heapq
nums = [38, 27, 43, 3, 9, 82, 10]
print("Original:", nums)
heapq.heapify(nums)
print("Heapified:", nums)
print("Min element:", nums[0])
heapq.heappush(nums, 1)
print("After push 1:", nums)
popped = heapq.heappop(nums)
print(f"Popped {popped}, heap: {nums}")
print()
print("Top 3 smallest:", heapq.nsmallest(3, [38, 27, 43, 3, 9, 82, 10]))
print("Top 3 largest:", heapq.nlargest(3, [38, 27, 43, 3, 9, 82, 10]))Heap operation complexities
| Operation | Time | Notes |
|---|---|---|
| Find min/max | O(1) | Root element |
| Insert | O(log n) | Bubble up |
| Extract min/max | O(log n) | Bubble down |
| Heapify (build) | O(n) | Bottom-up construction |
| Heap sort | O(n log n) | Extract min n times |
Key Takeaways
- Heaps keep the min (or max) at the root. Read it in O(1).
- Insert and extract are O(log n) via bubble-up and bubble-down.
- Building a heap from an array is O(n), not O(n log n).
- Python:
heapqmodule. Java:PriorityQueue. C++:priority_queue. - Key applications: Dijkstra’s algorithm, top-K problems, median maintenance, and task scheduling.