Using Heapq for Priority Queues

Python
import heapq

# Build a min-heap in place from a list
data = [5, 7, 9, 1, 3]
heapq.heapify(data)          # data is now heap-ordered, data[0] is smallest

heapq.heappush(data, 4)      # push new item, maintain heap invariant
smallest = heapq.heappop(data)  # pop and return smallest item

# Get n largest/smallest without fully sorting
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums))   # [42, 37, 23]
print(heapq.nsmallest(3, nums))  # [-4, 1, 2]

Progress:

• Step 1: Decide if you need a full priority queue, a one-off top-k query, or a merge operation
• Step 2: Choose the right heapq function(s) for the task
• Step 3: For priority queues with ties/mutability, wrap items as tuples (priority, counter, item)
• Step 4: For max-heap behavior, negate priorities (heapq only implements min-heap)
• Step 5: Test edge cases — empty heap, equal priorities, updating/removing entries

Core functions:

Choosing between approaches:

• n == 1: use min()/max() — faster
• n small, iterable large: use nlargest/nsmallest
• n ≈ len(iterable): use sorted(iterable)[:n] — faster than heap approach
• Repeated push/pop over time: use heappush/heappop directly on a heap list

Example 1: Priority queue with stable ordering and tie-breaking

Input: Tasks with priorities, need FIFO order for equal priorities

Python
import heapq
import itertools

counter = itertools.count()
pq = []

def add_task(task, priority=0):
    entry = (priority, next(counter), task)
    heapq.heappush(pq, entry)

def pop_task():
    priority, count, task = heapq.heappop(pq)
    return task

add_task('write code', priority=2)
add_task('write spec', priority=1)
add_task('create tests', priority=1)

Output: pop_task() calls return 'write spec', 'create tests', 'write code' — priority order, FIFO within same priority.

Example 2: K largest elements from a stream

Input: stream = [3, 1, 4, 1, 5, 9, 2, 6], need top 3

Python
import heapq
print(heapq.nlargest(3, stream))

Output: [9, 6, 5]

Example 3: Merging multiple sorted logs by timestamp

Input: Several already-sorted iterables of log entries

Python
import heapq
log1 = [1, 4, 7]
log2 = [2, 5, 8]
log3 = [3, 6, 9]
merged = list(heapq.merge(log1, log2, log3))

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Example 4: Max-heap via negation

Input: Need largest-first pop behavior

Python
import heapq
nums = [3, 1, 4, 1, 5, 9]
heap = [-n for n in nums]
heapq.heapify(heap)
largest = -heapq.heappop(heap)  # 9

Output: largest == 9