A priority queue answers one question repeatedly: which pending item should run next? Schedulers, retry systems, graph algorithms, simulations, and background workers all need some version of that operation.

A list can hold pending items, but finding the best one by scanning costs linear time each time. Keeping the whole list sorted makes retrieval cheap, but insertion has to preserve that full ordering.

Python’s heapq module uses a heap instead. A heap is partially ordered: it guarantees that the smallest item is at heap[0], but it does not keep every element globally sorted. Push and pop operations take logarithmic time, while reading the current minimum is constant time.

That mental model matters. heapq is an ordering primitive, not a complete scheduler. Correct applications still need to define tie-breaking, updates, cancellation, fairness, and concurrency behavior.

Start with the smallest useful queue

Suppose lower numbers mean more urgent work:

import heapq

pending = []

heapq.heappush(pending, (20, "send-report"))
heapq.heappush(pending, (5, "page-operator"))
heapq.heappush(pending, (10, "refresh-cache"))

priority, task = heapq.heappop(pending)

print(priority, task)

The first item removed is (5, "page-operator").

heapq implements a min-heap. Tuple comparison is lexicographic, so Python compares the priority first. The heap invariant is enough to keep the smallest entry at index 0.

Do not infer more than that guarantee:

print(pending)  # The internal list is not sorted output.

If you need every item in order, repeatedly pop entries, or use sorted() on a copy when the original heap must remain intact.

Equal priorities need an explicit tie-breaker

Pairs such as (priority, task) become fragile when priorities tie.

Consider tasks that do not define an ordering:

from dataclasses import dataclass

@dataclass
class Job:
    name: str

This can fail:

pending = []

heapq.heappush(pending, (10, Job("resize-image")))
heapq.heappush(pending, (10, Job("send-email")))

Once the priorities compare equal, tuple comparison moves to the task field. Python then tries to order the two Job objects, which raises TypeError.

Comparable task values can also produce the wrong policy. Equal-priority strings would be ordered by their text rather than by arrival time.

Use a unique sequence number as the second field:

import heapq
import itertools

pending = []
sequence = itertools.count()

heapq.heappush(pending, (10, next(sequence), Job("resize-image")))
heapq.heappush(pending, (10, next(sequence), Job("send-email")))

Comparison now proceeds by priority and then sequence number. Because sequence numbers are unique, Python never needs to compare the task objects. Equal-priority tasks are also returned in insertion order.

Encapsulate the ordering rule

If tie-breaking is part of the queue contract, callers should not have to remember the tuple shape.

import heapq
import itertools

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._sequence = itertools.count()

    def push(self, task, priority):
        entry = (priority, next(self._sequence), task)
        heapq.heappush(self._heap, entry)

    def pop(self):
        priority, _, task = heapq.heappop(self._heap)
        return task, priority

    def __bool__(self):
        return bool(self._heap)

Usage stays simple:

queue = PriorityQueue()
queue.push("refresh-cache", priority=20)
queue.push("page-operator", priority=5)

task, priority = queue.pop()

This is sufficient when entries are only added and removed from the front.

Raw heapq does not provide locking. If several threads need a synchronized producer-consumer queue, queue.PriorityQueue is a better starting point because it supplies the synchronization behavior that a bare list plus heapq lacks.

Do not update priorities by mutating heap entries

A common next requirement is reprioritizing work that is already pending.

Changing an arbitrary entry directly is unsafe:

# Wrong: this can violate the heap invariant.
queue._heap[index] = (1, sequence_number, task)

Heap correctness depends on ordering relationships between parents and children. Replacing an entry can break those relationships even though the object is still a valid Python list.

Calling heapq.heapify() would restore the heap, but rebuilding after every update costs linear time in the heap size. Frequent updates need a different design.

A standard approach is lazy deletion: keep a mapping to the current entry, mark obsolete entries as removed, and push a replacement with the new priority. The stale entry remains in the heap until it reaches the root, where it can be skipped safely.

Support updates and cancellation with lazy deletion

Here is a practical implementation:

import heapq
import itertools

_REMOVED = object()

class UpdatablePriorityQueue:
    def __init__(self):
        self._heap = []
        self._entries = {}
        self._sequence = itertools.count()

    def set(self, task, priority):
        if task in self._entries:
            self.remove(task)

        entry = [priority, next(self._sequence), task]
        self._entries[task] = entry
        heapq.heappush(self._heap, entry)

    def remove(self, task):
        entry = self._entries.pop(task)
        entry[2] = _REMOVED

    def pop(self):
        while self._heap:
            priority, _, task = heapq.heappop(self._heap)

            if task is _REMOVED:
                continue

            del self._entries[task]
            return task, priority

        raise KeyError("pop from an empty priority queue")

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

Reprioritizing a task now creates a new live entry:

queue = UpdatablePriorityQueue()

queue.set("retry-payment", 50)
queue.set("refresh-dashboard", 20)
queue.set("retry-payment", 3)

print(queue.pop())

The result is ("retry-payment", 3). The old priority-50 entry still exists physically, but it is marked with _REMOVED and will never be returned as live work.

The marker is a unique object() and the code checks it with is. A normal task value therefore cannot accidentally compare equal to the removal marker.

remove() deliberately raises KeyError for an unknown task because _entries.pop(task) does. A production API can choose a different contract, but it should make that contract explicit rather than silently hiding mistakes.

Lazy deletion trades simpler updates for extra memory

The mapping counts live tasks, while the heap can contain both live and stale entries.

If 10,000 live tasks are reprioritized repeatedly before they are popped, the physical heap can temporarily grow far beyond 10,000 entries. The stale entries disappear only as they reach the root.

For occasional updates, that overhead can be acceptable. For update-heavy workloads, periodically rebuilding from the live mapping can bound stale-entry growth:

self._heap = list(self._entries.values())
heapq.heapify(self._heap)

heapify() runs in linear time, so rebuilding after every update would undermine the lazy approach. A queue can instead rebuild when the physical heap becomes several times larger than the number of live entries.

That threshold is an application policy, not a heapq guarantee. Measure the workload before adding compaction logic.

Dictionary-backed updates require hashable task identities

The updatable design uses tasks as dictionary keys, so they must be hashable.

This fails:

queue.set(["resize", "photo.jpg"], 10)

Lists are mutable and unhashable.

For mutable payloads, use a stable identifier as the queue key and store the payload elsewhere. A job ID can identify the queue entry while a separate mapping or database holds the current job data.

This separation also improves maintainability: queue entries contain ordering metadata and stable identity instead of a large mutable object graph.

Priority values need clear business semantics

The heap orders values; it does not know what those values mean.

If smaller numbers mean more urgent work, document and test that rule. Otherwise a caller may reasonably assume that priority 100 outranks priority 10.

Named constants can make the policy visible:

PRIORITY_URGENT = 10
PRIORITY_NORMAL = 50
PRIORITY_BACKGROUND = 100

Priorities do not need to be consecutive.

For deadline scheduling, an absolute deadline can itself be the ordering key. For elapsed-time scheduling within one process, a monotonic clock is usually preferable to wall-clock time because wall-clock adjustments can jump forward or backward.

The heap still does not wait until a deadline. A surrounding scheduler must decide when to sleep, how to wake early when new work arrives, and what to do with overdue tasks.

Stable ordering is not the same as fairness

The sequence number provides FIFO behavior among tasks with equal priority. It does not guarantee that every task will eventually run.

If urgent work arrives continuously, low-priority work can remain queued indefinitely. That is starvation, and the heap is following the ordering policy exactly.

Applications that require fairness need a higher-level policy, such as limiting consecutive urgent jobs, aging waiting tasks toward higher effective priority, or allocating service among separate queues.

Those policies are scheduler decisions. heapq only orders the values it receives; it does not provide bounded waiting time.

Combined heap operations have different semantics

heapq also provides operations that combine a push and a pop.

heapq.heappushpop(heap, item) pushes the new item and then returns the smallest item. The new item participates in deciding what is removed.

heapq.heapreplace(heap, item) removes the current smallest item first and then pushes the replacement. It requires a non-empty heap, and the returned item can be larger than the inserted item.

They are useful for bounded-selection algorithms, but they are not interchangeable. For a task queue where every submitted task must stay pending until processed or cancelled, explicit heappush() and heappop() are usually clearer.

Common mistakes come from assuming too much

Several bugs follow from treating a heap like a sorted container.

Do not iterate over the internal list and expect priority order. Only the minimum-at-root property is guaranteed.

Do not use (priority, task) if equal priorities can occur and task values are not safely comparable. Add a unique tie-breaker.

Do not mutate an ordering field inside the heap. Replace the entry through heap operations or use lazy deletion for updates.

Do not assume heapq supplies concurrency semantics. It does not block for new work, enforce capacity, or synchronize multiple threads.

Know when a heap is the wrong tool

A heap is a strong fit when a program repeatedly inserts values and repeatedly needs the current minimum.

Simpler tools are often better in other cases:

  • If you collect all items once and then consume all of them in order, use sorted().
  • If you need only one minimum from a fixed collection, use min().
  • If multiple threads need a synchronized work queue, consider queue.PriorityQueue.
  • If the dataset is tiny and operations are rare, a list may be easier to maintain and fast enough.
  • If you need efficient arbitrary-range queries rather than repeated minimum extraction, choose a data structure designed for those queries.

The asymptotic cost of heap operations is useful, but real performance also includes stale-entry cleanup, synchronization, application logic, and memory behavior.

Conclusion

heapq works best when you treat it as a small, precise ordering primitive.

The heap guarantees that the smallest entry is at the root. A sequence number handles ties and prevents accidental task comparison. A mapping plus lazy deletion supports practical reprioritization and cancellation without mutating the heap in place.

Those patterns come with real trade-offs: stale entries can consume memory, dictionary-backed updates require hashable identities, and priority ordering alone provides neither fairness nor thread safety.

Start with the smallest queue that matches the problem, then add update tracking, compaction, or synchronization only when the workload requires it.

Python Data Structures Standard Library Algorithms