Priority Queue

The Idea

A priority queue hands out the most urgent item, whatever time it arrived. A heap is the natural engine: push and pop in O(log n), peek in O(1).

Python's heapq compares whatever you push, so push tuples. Convention is (priority, tiebreak, item) — tuples compare left to right, and the counter both keeps equal priorities in arrival order and stops Python from ever comparing the payloads.

Real-World Example

A container port berths ships by cost of waiting, not by who anchored first. A reefer full of thawing fish outranks a gravel barge that drifted in yesterday, and among equally urgent ships the earlier arrival goes in first.

The Code

import heapq, itertools

berth, tick = [], itertools.count()    # tick breaks ties, keeps FIFO

def request(priority, ship):
    heapq.heappush(berth, (priority, next(tick), ship))

def next_ship():
    return heapq.heappop(berth)[2]     # lowest number = most urgent

for p, s in [(2, "Kestrel"), (1, "Aurora"), (2, "Bellona")]:
    request(p, s)
print(next_ship())                     # Aurora
print(next_ship())                     # Kestrel - tied, but queued first

import heapq
dock = []
heapq.heappush(dock, (3, "Kestrel"))
heapq.heappush(dock, (1, "Aurora"))
# should print Aurora, the most urgent ship
print(heapq.heappop(dock)[___])