In a priority queue items leave not in arrival order but by priority: the smallest always goes first. This underlies task schedulers, Dijkstra and "k largest" problems. In this lesson we look at the ADT, three implementations and the practical use of heapq.
The ADT: push and pop_min
The ADT offers three operations: push(priority, item), pop_min() (extract-min) and peek(). Unlike an ordinary queue, the output order depends on priority, not arrival time. The smaller the priority, the more important the item; if we want the largest, we negate.
Three implementations
In an unsorted list push is O(1) but pop_min scans. In a sorted list bisect.insort finds the place in O(log n), but shifting items costs O(n) (bisect). A binary heap brings both down to O(log n): the tree is stored in an array, a parent is not larger than its children, and the minimum sits in h[0] (heaps).
