Binary heap explained: priority queues, code and complexity

What problem a heap solves

Many programs repeatedly need the most urgent item from a changing collection: the next event in a simulation, the closest unvisited node in Dijkstra's algorithm, the task with the highest priority, or the k largest values in a stream. Sorting the whole collection after every insert costs O(n log n) each time. A sorted list makes removal cheap but insertion O(n). A heap makes both insert and remove-min O(log n), which is exactly what a priority queue needs.

The idea: a tree stored in an array

A heap is a complete binary tree: every level is full except possibly the last, which is filled from the left. That shape lets us store the tree in a plain list with no pointers.

Two repair operations keep the heap property. Sift up: after appending a new item at the end, swap it with its parent while it is smaller. Sift down: after moving the last item to the root, swap it with its smaller child while it is larger than that child. Each operation moves along one root-to-leaf path, so it does at most about log2(n) swaps.

Worked example: push and pop

Start with the min-heap [2, 5, 3, 9, 6] (2 is the root, its children are 5 and 3, and 5 has children 9 and 6).

1. Push 1: append it, giving [2, 5, 3, 9, 6, 1]. Index 5 has parent index 2 (value 3).
2. 1 is smaller than 3, swap: [2, 5, 1, 9, 6, 3]. Now index 2 has parent index 0 (value 2).
3. 1 is smaller than 2, swap: [1, 5, 2, 9, 6, 3]. It reached the root, stop.
4. Pop: remove the root 1, move the last item 3 to the root: [3, 5, 2, 9, 6].
5. Children of the root are 5 and 2; the smaller is 2, and 3 is larger, swap: [2, 5, 3, 9, 6]. Index 2 has no children, stop. The pop returned 1.

Python implementation of a min-heap

This class shows the mechanics. In real code use heapq, shown in the next section.

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

Priority queues with Python heapq

The heapq module works on an ordinary list and always keeps it a min-heap. heapify turns an existing list into a heap in place in O(n). To use priorities, push tuples: Python compares tuples element by element, so the first element is the priority. Add a counter as a tie-breaker so that items with equal priority never need to be compared directly.

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

For a max-heap, Python 3.14 added heapq.heapify_max, heapq.heappush_max and heapq.heappop_max. On older versions, the usual trick is to push negated keys, for example heapq.heappush(h, -score), and negate again when you pop.

Time and space complexity

Building a heap by calling push n times costs O(n log n). heapify sifts down from the last parent to the root and costs O(n), so prefer it when you already have all the items.

Variants and common mistakes

• Max-heap: the same code with the comparison reversed; in Python, use the _max functions (3.14 and later) or negate the keys.
• d-ary heap: each node has d children. A shallower tree makes push cheaper and pop slightly more expensive.
• Indexed priority queue / decrease-key: heapq cannot change the priority of an item in place. A common workaround (used in Dijkstra's algorithm) is to push a new entry and skip outdated entries when they are popped.
• Comparing incomparable items: pushing (priority, dict) raises TypeError when two priorities are equal, because Python then compares the dicts. Add a counter as the second tuple element.
• Treating the heap list as sorted. Only heap[0] is guaranteed; use sorted(heap) if you need everything in order.
• Off-by-one errors when mixing 1-based formulas (children 2i and 2i + 1) from textbooks with 0-based Python lists.

When to use a heap and typical problems

Use a heap when you repeatedly need only the smallest or largest item from a collection that keeps changing. Use a sorted list or balanced tree when you also need ordered iteration or arbitrary deletions, and a plain min() when you only need the minimum once.

Classic uses: Dijkstra's shortest path and Prim's minimum spanning tree, merging k sorted lists (heapq.merge), finding the k largest or smallest items (keep a heap of size k, O(n log k)), the running median (two heaps), task schedulers and event-driven simulations, and heapsort.