To build a priority queue in Python, keep a list, insert entries with heapq.heappush(), and remove the smallest with heapq.heappop(). Insertion and removal take O(log n), while reading the smallest entry at heap[0] takes O(1). Because heapq implements a min-heap, lower numeric values leave first.

A regular queue preserves arrival order; a priority queue serves the most urgent eligible item. Typical uses include schedulers, shortest-path algorithms, support tickets, simulations, and stream merging. The module belongs to the standard library. For a broader foundation in queues and complexity, read Python data structures and algorithms.

How the heapq heap works

A binary heap maintains one key invariant: every parent is less than or equal to its children. The underlying list is not fully sorted. Only its minimum is guaranteed at position zero. This partial ordering is why inserting a task is cheaper than sorting the complete queue after every change.

import heapq

jobs = []
heapq.heappush(jobs, (2, "generate report"))
heapq.heappush(jobs, (1, "restore service"))
heapq.heappush(jobs, (3, "archive logs"))


while jobs:
priority, job = heapq.heappop(jobs)
print(priority, job)

Priority 1 appears first. Tuples compare field by field, so the task text breaks equal-priority ties here. The official heapq documentation also describes heapify(), heappushpop(), heapreplace(), nsmallest(), and nlargest().

If entries already exist in a list, heapq.heapify(entries) transforms it in O(n). Pushing n entries one by one costs O(n log n). Do not call sort() after each insertion: it pays for a complete ordering the queue does not need. The guide to Python list operations explains the costs behind list insertion and removal.

Handle equal priorities with a counter

An entry shaped as (priority, task) can fail when equal priorities force Python to compare task objects that have no ordering. Even comparable strings silently use alphabetical order rather than arrival order. Include an increasing counter and store (priority, sequence, task) to make ties stable and safe.

import heapq
from dataclasses import dataclass
from itertools import count

@dataclass
class Task:
name: str
customer: str


sequence = count()
queue = []


def add(priority: int, task: Task) -> None:
heapq.heappush(queue, (priority, next(sequence), task))


add(1, Task("fix payment", "Store A"))
add(1, Task("release order", "Store B"))
add(2, Task("export metrics", "Internal"))


while queue:
priority, _, task = heapq.heappop(queue)
print(priority, task.name)

The counter preserves first-in order among equal priorities and prevents comparison between Task instances. A data class makes each record readable; see Python data classes for defaults, ordering, and immutable models.

Serve larger priorities first

With the traditional min-heap API, negate a numeric key to model maximum priority. The largest original number becomes the smallest stored number. Negate only the key and restore it when popping:

import heapq

queue = []
heapq.heappush(queue, (-100, "critical incident"))
heapq.heappush(queue, (-20, "sales question"))


negative_priority, ticket = heapq.heappop(queue)
priority = -negative_priority
print(priority, ticket)  # 100 critical incident

Document whether 1 means urgent or low priority. Many production failures come from contradictory conventions between producers and consumers, not from the heap implementation. An Enum can clarify discrete severity levels; the Python Enum guide gives practical patterns.

Real case: update and cancel scheduled work

heapq does not provide efficient lookup, deletion, or priority update by ID. Finding and mutating an arbitrary entry can break the invariant. Schedulers commonly keep a dictionary of current entries, mark the old entry as removed, and push a replacement. Stale entries are skipped when they reach the top, an approach called lazy deletion.

import heapq
from itertools import count

REMOVED = object()
heap = []
active = {}
sequence = count()


def add(task_id, priority, payload):
if task_id in active:
cancel(task_id)
entry = [priority, next(sequence), task_id, payload]
active[task_id] = entry
heapq.heappush(heap, entry)


def cancel(task_id):
entry = active.pop(task_id)
entry[3] = REMOVED


def pop():
while heap:
priority, _, task_id, payload = heapq.heappop(heap)
if payload is not REMOVED:
del active[task_id]
return task_id, priority, payload
raise KeyError("empty priority queue")


add("job-7", 5, {"type": "email"})
add("job-7", 1, {"type": "urgent email"})
print(pop())

The dictionary provides average O(1) access to the current entry; the heap still selects the next job in O(log n). Removed entries consume memory until they reach the top. A workload with many updates and few removals may periodically rebuild the heap from active entries.

heapq, PriorityQueue, or bisect?

heapq is lightweight and unsynchronized, making it ideal for algorithms and single-threaded control flow. queue.PriorityQueue wraps a heap with locking and blocking operations for thread producers and consumers. The official queue documentation covers put(), get(), capacity, and task_done(). Multiple processes or distributed workers require a different coordination system.

bisect.insort() maintains a fully sorted list. Locating the insertion point is O(log n), but shifting list elements is O(n). It is useful when the program often traverses every item in order or accesses arbitrary positions. The official bisect documentation details this tradeoff. If the dominant operation repeatedly removes the minimum, a heap usually wins.

Common mistakes

  • Appending directly: append() does not restore the invariant; call heappush().
  • Assuming the list is sorted: only heap[0] has a guaranteed position.
  • Calling pop(0): it costs O(n) and does not restore the heap; use heappop().
  • Ignoring ties: place a sequence counter before non-comparable objects.
  • Mutating a priority: insert a replacement or heapify; use lazy deletion for frequent updates.
  • Sharing across threads: heapq has no locking; synchronize access or use PriorityQueue.

Implementation checklist

  • Document whether smaller or larger numbers mean greater urgency.
  • Shape entries as (priority, sequence, item).
  • Use heapify() when loading an existing batch.
  • Remove with heappop() and handle an empty queue explicitly.
  • Plan cancellation, reprioritization, and stale-entry cleanup.
  • Choose PriorityQueue when worker threads must block safely.
  • Test ties, emptiness, negative priorities, and realistic volume.

Keep queue policy separate from task execution so each part can be tested. The guidance in Python Clean Code helps avoid hidden conventions and oversized worker functions.

Frequently asked questions

Does heapq create a min-heap or max-heap?

The traditional API creates a min-heap, so the smallest entry is on top. To pop larger numeric priorities first, negate the key or use maximum-heap APIs available in the Python version adopted by your project.

Can I sort a heap to display the queue?

You can sort a copy without affecting the original. Never rely on internal order beyond index zero. To consume entries in priority order, repeatedly call heappop() on a copy.

Is heapq thread-safe?

It provides no synchronization. Protect all access with your own locking when appropriate, or use queue.PriorityQueue, designed for safe communication between threads.

When is a sorted list better?

It can be better when you frequently traverse every item in order, need arbitrary positions, or hold very few items. For repeated insertion and removal of the priority extreme, a heap generally scales better.