Definition
An AVL tree is a binary search tree that rebalances itself with rotations, so operations stay O(log n). A heap is a tree-shaped structure where each parent is smaller than its children (a min-heap), so the smallest item is always on top. Python's heapq provides one.
In simple words
A plain search tree can become a long, slow chain if you insert sorted data. An AVL tree keeps straightening itself out. A heap is a hospital queue: the most urgent patient is always next, and the rest don't need to be fully sorted.
Why it matters
Heaps power priority queues, the A* search algorithm, and picking the top-k items. Balanced trees underlie databases and many libraries.
How it works
| Operation | AVL tree | Heap |
|---|---|---|
| Find smallest | O(log n) | O(1) |
| Insert | O(log n) | O(log n) |
| Remove smallest | O(log n) | O(log n) |
| Find any value | O(log n) | O(n) |
In code
import heapq
patients = []
heapq.heappush(patients, (3, "Cold"))
heapq.heappush(patients, (1, "Accident"))
heapq.heappush(patients, (2, "Fever"))
while patients:
priority, problem = heapq.heappop(patients)
print(priority, problem)
scores = [40, 91, 75, 88, 60, 99]
print("Top 3:", heapq.nlargest(3, scores))
print("Bottom 2:", heapq.nsmallest(2, scores))Output
1 Accident 2 Fever 3 Cold Top 3: [99, 91, 88] Bottom 2: [40, 60]
Common mistakes
- Assuming a heap list is fully sorted. Only the first item is guaranteed.
- Sorting a huge list just to get the top 5. heapq.nlargest is cheaper.
Check yourself
Summary
- AVL trees rebalance to stay O(log n).
- Heaps give the smallest item instantly.
- heapq builds priority queues.
Finished reading?