Heaps and priority queues

Why a priority queue

A normal queue serves people in arrival order. Many real systems need a different rule: serve the MOST URGENT first. A hospital emergency desk treats a heart attack before a sprained ankle, even if the ankle arrived first. A ride-hailing app offers a trip to the nearest free driver. An operating system runs high-priority jobs first. A data structure that always gives you the item with the best priority is called a priority queue.

You could keep a sorted list, but inserting into it costs O(n) because items shift. You could keep an unsorted list, but finding the best item costs O(n). A heap does both jobs in O(log n).

What a heap is

A binary heap is a complete binary tree (every level full except maybe the last, which fills from the left; see Module 7) stored in an array. The node at index i has children at 2i + 1 and 2i + 2 and its parent at (i − 1) // 2. In a min-heap, every parent is less than or equal to its children; this is the heap property. So the smallest item is always at index 0, the root. A max-heap is the mirror: every parent is greater than or equal to its children.

A heap is NOT sorted. Only the parent-child rule holds; two siblings, or two nodes on different branches, can be in any order. That weaker rule is exactly what makes updates cheap.

Push and pop walk one path between the root and a leaf, and a complete tree has height about log₂ n, so they are O(log n). Heapify is O(n), not O(n log n), because most nodes sit near the bottom and can only move a step or two down; the few nodes near the top that can move far are rare. That makes heapify cheaper than pushing items one by one.

def push(heap, x):
    heap.append(x)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break                      # the heap property holds again
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent

h = []
for x in [5, 1, 8, 3, 2]:
    push(h, x)
print(h)   # Output: [1, 2, 8, 5, 3]

Python heapq

The heapq module turns a plain list into a min-heap. heappush(h, x) and heappop(h) are O(log n); h[0] is the smallest item; heapify(lst) rearranges a list in place in O(n). heapq.nlargest(k, items) and heapq.nsmallest(k, items) return the top k directly.

import heapq

h = []
for x in [5, 1, 8, 3, 2]:
    heapq.heappush(h, x)
print(h, h[0])                            # Output: [1, 2, 8, 5, 3] 1
print(heapq.heappop(h), heapq.heappop(h))  # Output: 1 2
nums = [9, 4, 7, 1, 8]
heapq.heapify(nums)
print(nums)                               # Output: [1, 4, 7, 9, 8]

Max-heaps: negate the values

heapq only gives a min-heap. The usual trick for a max-heap is to push −x and negate again when you read: the smallest negative is the largest original number. (Python 3.14 added max-heap functions such as heapq.heappush_max, but many online judges and the browser runner here use older versions, so learn the negation trick.)

mx = []
for x in [5, 1, 8, 3]:
    heapq.heappush(mx, -x)
print(-mx[0], -heapq.heappop(mx))   # Output: 8 8

Priorities with tuples and tie-breakers

To store items with a priority, push tuples (priority, item). Tuples compare item by item, so the priority decides first. If two priorities are equal, Python compares the next item, which can be a surprise: strings compare alphabetically, and dicts or custom objects cannot be compared at all.

tasks = []
heapq.heappush(tasks, (2, "write report"))
heapq.heappush(tasks, (1, "fix outage"))
heapq.heappush(tasks, (2, "answer email"))
print([heapq.heappop(tasks)[1] for _ in range(3)])
# Output: ['fix outage', 'answer email', 'write report']

q = []
heapq.heappush(q, (1, {"id": 7}))
heapq.heappush(q, (1, {"id": 3}))
# TypeError: '<' not supported between instances of 'dict' and 'dict'

The fix is a tie-breaker: push (priority, counter, item), where counter increases with every push. Equal priorities are then served in arrival order (first come, first served), and the item itself is never compared.

Common mistakes

• Thinking the heap list is sorted and reading h[1] as the second smallest. Fix: only h[0] is special; pop to get items in order.
• Forgetting that heapq is a min-heap. Fix: negate values for a max-heap, and negate back when you read.
• Pushing (priority, item) where items are dicts or objects. Fix: (priority, counter, item).
• Using sorted() on every insert to keep a priority list. That is O(n log n) per insert. Fix: heappush, O(log n).
• Popping from an empty heap: heapq.heappop([]) raises IndexError. Fix: check if h: first.