Python heapq priority updates: skip stale entries

Operation contract

A dispatcher ranks one parcel at priority 7, then raises it to priority 2. Pushing another tuple does not remove the old one. A map records the current priority and sequence for each parcel; pop discards tuples that no longer match. A monotonic sequence breaks equal-priority ties without comparing parcel objects. Top-k selection needs less bookkeeping when priorities never change.

Failure and ownership boundary

This is lazy deletion. Many revisions without draining grow heap memory even if the current map has one key. Rebuild from current entries above a measured stale-entry threshold. The parcel identifier must remain a stable hash key; mutable hash keys break lookup.

Working program

import heapq
from itertools import count

pending = []
current = {}
sequence = count()
stale = 0

def set_priority(parcel_id, priority):
    revision = next(sequence)
    current[parcel_id] = (priority, revision)
    heapq.heappush(pending, (priority, revision, parcel_id))

def take_next():
    global stale
    while pending:
        priority, revision, parcel_id = heapq.heappop(pending)
        if current.get(parcel_id) != (priority, revision):
            stale += 1
            continue
        del current[parcel_id]
        return parcel_id
    return None

set_priority("P-47", 7)
set_priority("P-48", 5)
set_priority("P-47", 2)
print(take_next())
print(take_next())
print(take_next())
print("stale:", stale)

Output

P-47
P-48
None
stale: 1

Costs and limits

Each push and pop takes O(log h) for h heap entries. Storage follows total revisions until stale entries are drained or compacted.

Common Mistakes

• A new priority does not remove the old tuple.
• Do not compare arbitrary task objects to break ties.
• Do not ignore stale-entry memory under frequent updates.

Connected lessons

Python heapq top-k: define ties before ranking frequencies, Python hash and equality: immutable dictionary keys, Python running median: two heaps with an exact even-count result.