Priority queues and binary heaps in Python

Suppose several tasks are waiting and you need the one with the smallest priority number next. You can keep a fully sorted list, but that maintains more ordering than this question needs. A priority queue provides the next item by priority; the binary heap below maintains just enough order to answer that question.

What a binary heap guarantees#

A binary heap has the shape of a complete binary tree: fill each level before the next, from left to right. Store it in an array. For a zero-based index k, the children are at 2k + 1 and 2k + 2 when those positions exist. No separate pointers are needed for these parent-child links.

In a min-heap, each parent is no greater than its children. Following that rule from any item back to the root shows why the root is a minimum. The rule does not order siblings. In [1, 4, 2, 7, 6, 3], the children of 1 are 4 and 2, and 4 appearing first does not violate it.

Remove the root in the experiment. The last item moves into the empty root position, then moves down by swapping with the smaller child until the rule holds again. This is called sifting down. Adding an item does the opposite: append at the next position and move it up while it is smaller than its parent. Equal keys are allowed.

A max-heap reverses the comparison and keeps a maximum at the root. These names describe the retrieval rule, not whether a large number means an urgent task. The application chooses that meaning. Python’s heapq documentation defines both invariants; Python 3.14 added the public heapify_max, heappush_max and heappop_max functions. The examples here use the older min-heap API and work on Python 3.9 and later.

Python heapq example#

This complete example heapifies an existing list, reads its minimum, inserts a new value and removes values in priority order. The input numbers are illustrative. The array’s internal layout is not the output contract; the popped values are.

from heapq import heapify, heappop, heappush

heap = [4, 7, 2, 6, 1, 3]
heapify(heap)                 # rearrange this list into a min-heap
print(heap[0])                # 1: inspect without removing
heappush(heap, 0)
print(heappop(heap))          # 0: remove the new minimum
print([heappop(heap) for _ in range(len(heap))])
# [1, 2, 3, 4, 6, 7]
print(heap)                   # []: repeated pops consumed it

heapify changes the list in place. Start with list(values) if the original must stay intact. Both heap[0] and heappop(heap) raise IndexError on an empty list, so check whether it contains anything first. Appending directly to a heap list can break its invariant; use heappush to maintain it.

Binary heap time complexity#

A complete binary tree has O(log n) height. Insertion repairs one path upwards; removing the root repairs one path downwards. Neither operation needs to sort every pair of items. The following bounds count heap work with constant-cost key comparisons; memory allocation and expensive comparison functions can add other costs.

Building with repeated pushes takes O(n log n) work in the worst case, while bottom-up heapify takes O(n). Nodes near the leaves need little or no downward repair; the few nodes near the root can travel farther. Princeton’s priority-queue material derives this linear construction bound. Storage for the heap is O(n); the full output list in our examples also takes O(n).

The neighbouring operations can have different costs in a library. Java SE 25’s PriorityQueue documents logarithmic enqueuing and dequeuing, constant-time peek, and linear contains(Object) and remove(Object). Removing the next item and locating a particular item are different tasks.

Keep equal priorities in arrival order#

For records, store a comparison key alongside the task. A pair (priority, task) has a trap: when priorities tie, Python compares the task values next. Two dictionaries do not have the ordering needed for that comparison.

Add a unique increasing counter between the priority and task. Earlier arrivals then win ties, and comparison never reaches the task object. This is an explicit policy you supply to the heap, as described in Python’s priority-queue implementation notes.

from heapq import heappop, heappush
from itertools import count

def ordered_tasks(entries):
    # Lower numbers mean higher priority in this example.
    heap = []
    arrival = count()
    for priority, task in entries:
        heappush(heap, (priority, next(arrival), task))
    return [heappop(heap)[2] for _ in range(len(heap))]

tasks = [
    (2, {"name": "compile"}),
    (1, {"name": "urgent check"}),
    (2, {"name": "collect assets"}),
]
print([task["name"] for task in ordered_tasks(tasks)])
# ['urgent check', 'compile', 'collect assets']

The urgent check comes first despite arriving second. Compile then precedes collect assets because their priorities tie and compile has the lower counter. The tasks and their numbers are illustrative; this function orders a finite batch and does not execute tasks, cancel them or provide thread coordination.

Iteration, updates and heap limits#

Iterating the backing array gives its current arrangement. Python’s heap invariant allows unsorted siblings; Java’s iterator explicitly offers no ordering guarantee. Repeatedly pop to consume values in priority order, or sort a copy with the same comparison rule for a full listing. Merely printing a heap does neither.

Do not change a stored comparison key and expect the heap to repair itself. Remove and reinsert using an appropriate interface, or push a fresh entry and identify old entries as stale when they are popped. Lazy deletion needs an identity or version check and can retain extra entries; the simple batch function above does not implement it. Python heapq has no public indexed decrease-key operation.

A heap is useful when the next minimum or maximum matters repeatedly. If you only need one minimum, a linear scan may be enough. If you need a fully ordered result once, sorting is often the clearer task. If you need repeated exact membership checks, a heap’s parent-child rule does not help locate arbitrary values; binary search explains lookup in an already sorted array. A linked list provides a different trade-off around positions and updates, rather than heap ordering.

For a dependency graph, priority can choose among tasks that are already eligible. It cannot make a blocked task safe to run. Topological sorting shows how unmet prerequisites decide the ready set before a queue or heap chooses its next member. Dijkstra’s shortest-path visualiser explores a different use of choosing by a changing distance estimate.