Heaps & Priority Queues

Always grab the smallest (or largest) cheaply

A priority queue hands you the highest-priority item next, not the oldest. A heap is the data structure that implements it: it keeps the min (or max) at the top so you can peek it in O(1) and pop it in O(log n), and push a new item in O(log n).

It does not keep everything fully sorted — that would be more work. It only guarantees cheap access to the extreme, which is exactly what you need when you repeatedly want 'the next-most-urgent thing'.