heapq turns a list into a heap
import heapq
tasks = []
heapq.heappush(tasks, 5)
heapq.heappush(tasks, 1)
heapq.heappush(tasks, 8)
heapq.heappush(tasks, 3)
print("smallest:", tasks[0])
while tasks:
print(heapq.heappop(tasks), end=" ")
print()
nums = [9, 4, 7, 1, 8]
heapq.heapify(nums) # O(n): rearrange an existing list into a heap
print(nums[0])Output
smallest: 1 1 3 5 8 1
A max-heap: flip the sign
heapq is always a min-heap. To get the biggest first, push negative numbers:
import heapq
scores = [40, 95, 72, 88]
heap = [-s for s in scores]
heapq.heapify(heap)
print("highest:", -heapq.heappop(heap))
print("next:", -heapq.heappop(heap))Output
highest: 95 next: 88
Priorities with tuples
Tuples are compared item by item, so (priority, name) sorts by priority first:
import heapq
er = []
heapq.heappush(er, (3, "sprained ankle"))
heapq.heappush(er, (1, "heart attack"))
heapq.heappush(er, (2, "broken arm"))
heapq.heappush(er, (1, "breathing problem"))
while er:
priority, patient = heapq.heappop(er)
print(priority, patient)Output
1 breathing problem 1 heart attack 2 broken arm 3 sprained ankle
Tip: When priorities tie, the next item in the tuple decides. Here “breathing problem” comes before “heart attack” alphabetically.