Selecting the next item by priority
An ordinary FIFO queue follows arrival order; a priority queue compares designated keys. A min-oriented queue removes a current minimum, while a max-oriented one removes a maximum. New entries can arrive between removals.
The interface specifies behavior rather than requiring a binary heap. Ordered arrays, unordered arrays, and linked representations also implement it, distributing insertion, selection, and removal costs differently. A heap is one common representation of the abstraction.
References: [1]
Equal priorities need a tie policy
Equal priority does not necessarily imply first-in-first-out behavior. A stable policy can add a monotonically increasing sequence number as a tie-breaker, ordering equal-priority entries by arrival.
Python heapq documents entries containing priority, count, and task. Distinct counts also prevent comparison from reaching task objects that have no natural ordering. Stability and fairness depend on such explicit rules rather than the word queue.
References: [2]
Maintaining order when pending work changes
Pending work can be canceled or reprioritized. Changing a key inside a heap can invalidate parent–child order, requiring repositioning or a strategy that recognizes obsolete entries.
The heapq example uses a dictionary to locate current entries, marks old ones removed, and inserts replacements. Popping skips invalid records. Such lazy removal retains obsolete storage until cleanup, so logical pending work and physical occupancy are distinct resource measures.