Back
+20 XP
Concept

Priority Queues & Binary Heaps with heapq

`heapq` implements a binary min-heap over standard Python lists. The smallest element is always at index `0`. `.heappush()` and `.heappop()` maintain heap properties in $O(\log n)$ ⛰️.

python
import heapq

pq = []
heapq.heappush(pq, 45)
heapq.heappush(pq, 10)
heapq.heappush(pq, 30)

print(heapq.heappop(pq))  # 10 (smallest item popped first!) ⛰️
print(heapq.heappop(pq))  # 30

# 5. Priority Queues & Binary Heaps with heapq `heapq` implements a binary min-heap over standard Python lists. The smallest element is always at index `0`. `.heappush()` and `.heappop()` maintain heap properties in $O(\log n)$ ⛰️. ```python import heapq pq = [] heapq.heappush(pq, 45) heapq.heappush(pq, 10) heapq.heappush(pq, 30) print(heapq.heappop(pq)) # 10 (smallest item popped first!) ⛰️ print(heapq.heappop(pq)) # 30 ``` Priority queues are essential for Dijkstra's shortest path, event simulators, and task schedulers where urgent jobs jump ahead of low-priority tasks! ⛰️ --- ### Question What invariant does Python's `heapq` module guarantee about `heap[0]`? 🧠 - [ ] a. It is always the minimum element in the entire heap ⛰️ - [ ] b. It is always the most recently added item - [ ] c. It is always the maximum element - [ ] d. It contains the length of the heap --- ### Challenge Import `heapq`. Create list `h = [50, 20, 80]`. Transform into heap with `heapq.heapify(h)`. Push `5` using `heapq.heappush(h, 5)`. Pop and print the smallest element. 🎯 <details> <summary>Solution</summary> ```python import heapq h = [50, 20, 80] heapq.heapify(h) heapq.heappush(h, 5) print(heapq.heappop(h)) ``` </details>

Checkpoint

What invariant does Python's `heapq` module guarantee about `heap[0]`? 🧠

Practice

Import `heapq`. Create list `h = [50, 20, 80]`. Transform into heap with `heapq.heapify(h)`. Push `5` using `heapq.heappush(h, 5)`. Pop and print the smallest element. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks