Heaps and priority queues

A heap always keeps its smallest item at the front. Adding or removing an item costs O(log n), and looking at the smallest costs O(1). Reach for one when a question asks for the top k items or the next most urgent job.

60
[95, 88, 79]
5

Python's heapq is a min-heap. For a max-heap, push negative numbers and negate them again when you pop. Keeping a heap of only k items, as kth_largest does, costs O(n log k) instead of sorting everything.

Jobs by priority

1 Fix login bug
2 Reply to client
3 Update blog

Tuples compare by their first item, so the lowest priority number comes out first. Add a job with priority 0 and run it again.