Priority Queue Explained: heapq, Tuples and Tie-Breaking

A priority queue answers one question over and over: which waiting item is the most urgent right now? Not the oldest, not the newest, the most urgent. In Python the answer is almost always heapq, and almost every bug people write with it comes from the same place: what they push onto it. This article covers the heap underneath, the (priority, counter, item) tuple convention, and the two operations heapq does not give you, changing a priority and serving the largest first.

The problem it solves

You need a collection where items arrive in any order and leave in priority order, with arrivals and departures interleaved. Three obvious designs each fail one side:

• An unsorted list: push is O(1), but every pop scans for the minimum, O(n).
• A sorted list: pop from the end is O(1), but every push shifts elements to keep the order, O(n).
• Sorting once: only works if nothing arrives after you start serving.

A binary heap makes both sides O(log n). It does not keep the items sorted. It keeps one weaker promise, that every parent is no larger than its children, and that promise is enough to know the root is the minimum.

The intuition

A heap is an array read as a tree: the children of index i sit at 2i + 1 and 2i + 2. A new item goes into the next free slot at the end and sifts up, swapping with its parent while it is more urgent. Popping takes the root, moves the last item into the hole and sifts down, swapping with the smaller child until the rule holds again. Both walks follow a single root-to-leaf path, and a complete tree of n items is about log2(n) levels deep.

heapq orders whatever you push with the ordinary < operator. That is why entries are tuples. Tuples compare left to right, so (priority, counter, item) means: priority first; among equal priorities, the smaller counter, which is the earlier arrival; and the item itself is never compared, because counters are unique. Drop the counter and two things break. Equal priorities come out in whatever order the heap happens to hold them, and if the payloads cannot be compared, a tie raises an exception.

Watch it run

The animation is the lesson's berth queue. Kestrel requests at priority 2, tick 0, and alone it is the most urgent ship there is. Aurora arrives at priority 1, a reefer full of thawing fish, and lands at the end of the array first. It is compared with its parent, 1·1 against 2·0, and because the lower number wins it climbs to the root in one swap, not a re-sort. Bellona pushes at priority 2, tick 2, and against Aurora's 1 it does not climb at all. Tuples compare left to right, so Kestrel's (2, 0) beats Bellona's (2, 2): tied priority, earlier tick. next_ship() pops the root, Aurora, regardless of arrival order. The last entry takes the empty root and sinks; Kestrel and Bellona are tied on priority, so the tick decides and Kestrel rises. The next pop is Kestrel. Push and pop are both O(log n).

The code

The lesson's queue, extended to drain completely. Peeking is reading index 0, because the root is always the minimum:

import heapq
import itertools

berth, tick = [], itertools.count()

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

def next_ship():
    return heapq.heappop(berth)[2]

for p, s in [(2, "Kestrel"), (1, "Aurora"), (2, "Bellona")]:
    request(p, s)
print(berth[0][2])                  # Aurora   -- peek is O(1): the root
print(next_ship(), next_ship(), next_ship())   # Aurora Kestrel Bellona

Without the counter, a tie falls through to the payload. Dictionaries do not support <:

plain = []
heapq.heappush(plain, (2, {"ship": "Kestrel"}))
try:
    heapq.heappush(plain, (2, {"ship": "Bellona"}))   # tie: Python compares the dicts
except TypeError as err:
    print(type(err).__name__)       # TypeError

heapq has no "change this item's priority". Finding an item inside a heap is O(n), so the usual answer is lazy deletion: keep a map from item to its live entry, mark the old entry dead, push a new one, and skip dead entries when popping:

class PriorityQueue:
    """Min-priority queue with FIFO ties and change_priority by lazy deletion."""
    def __init__(self):
        self.heap = []
        self.live = {}                    # item -> its current entry
        self.tick = itertools.count()

    def push(self, item, priority):
        if item in self.live:             # re-pushing an item means "change it"
            self.live.pop(item)[2] = None # mark the old entry dead, O(1)
        entry = [priority, next(self.tick), item]
        self.live[item] = entry
        heapq.heappush(self.heap, entry)

    def pop(self):
        while self.heap:
            priority, _, item = heapq.heappop(self.heap)
            if item is not None:          # skip entries marked dead
                del self.live[item]
                return item, priority
        raise IndexError("pop from an empty priority queue")

    def __len__(self):
        return len(self.live)

pq = PriorityQueue()
pq.push("gravel", 5)
pq.push("fish", 1)
pq.push("timber", 3)
pq.push("gravel", 0)                      # the gravel is suddenly urgent
print(len(pq), len(pq.heap))              # 3 4  -- one dead entry still inside
print([pq.pop() for _ in range(len(pq))])
# [('gravel', 0), ('fish', 1), ('timber', 3)]

heapq is a min-heap only. For largest-first, negate the priority and leave the counter positive, so ties still leave in arrival order:

jobs = []
for prio, name in [(3, "resize"), (9, "page-alert"), (9, "db-alert")]:
    heapq.heappush(jobs, (-prio, next(tick), name))
print([heapq.heappop(jobs)[2] for _ in range(3)])
# ['page-alert', 'db-alert', 'resize']

Checked on 500 seeded random sequences of pushes, priority changes and pops against a brute-force reference that scans every live item for the smallest (priority, arrival):

import random

def brute_pop(entries):
    """Reference: scan everything for the smallest (priority, arrival)."""
    best = min(entries, key=lambda item: entries[item])
    return best, entries.pop(best)

random.seed(28)
ok = True
for _ in range(500):
    pq, ref, arrival = PriorityQueue(), {}, itertools.count()
    for _ in range(random.randint(1, 60)):
        if ref and random.random() < 0.35:
            item, (prio, _) = brute_pop(ref)
            ok &= pq.pop() == (item, prio)
        else:
            item, prio = random.choice("abcdefgh"), random.randint(0, 4)
            pq.push(item, prio)               # new item or a priority change
            ref[item] = (prio, next(arrival))
        ok &= len(pq) == len(ref)
    while ref:
        item, (prio, _) = brute_pop(ref)
        ok &= pq.pop() == (item, prio)
print(ok)                                 # True

The complexity

• Push and pop: O(log n), one root-to-leaf path each.
• Peek: O(1), the root at index 0.
• Build from n items: O(n) with heapq.heapify, cheaper than n pushes; heapify in linear time explains why.
• Change priority, lazily: O(log n) for the new push. Dead entries stay until popped, so the heap can hold more entries than live items; if changes are frequent, rebuild when dead entries outnumber live ones.
• Space: O(n). The Big-O cheat sheet lists these next to the other heap operations.

Where it goes wrong

• Pushing bare payloads or (priority, item). Works until the first tie between items that cannot be compared, which may be in production.
• Assuming the list is sorted. Only index 0 is guaranteed. heap[1] is not the second smallest in general.
• Negating the counter for a max-heap. Negate only the priority, or ties come out newest first.
• Searching the heap to change a priority. That is O(n) per change; use a live-entry map and lazy deletion.
• Using queue.PriorityQueue for single-threaded code. It wraps the same heap in locks, which you pay for without needing.

When it shows up in interviews

Constantly, usually unnamed. Dijkstra's frontier is a priority queue with lazy deletion, as in Dijkstra step by step. Merging k sorted lists keeps one head per list in a heap. The task scheduler serves the most frequent task first, and top-k problems keep a heap of size k. Interviewers often follow up with "what happens on ties?" or "how would you change a priority?", which is exactly where the tuple and lazy deletion come in.

How to say it in an interview

"I'd use a binary heap: push and pop are O(log n) because each walks one root-to-leaf path, and peek is O(1) at the root. In Python I push tuples of priority, a counter and the item, so ties leave in arrival order and the payloads are never compared. For largest-first I negate the priority. heapq cannot update an entry in place, so to change a priority I mark the old entry dead in a map, push a new one and skip dead entries on pop."