Heaps and Priority Queues

Understand binary heaps and priority queues: the heap property, array layout, sift up and down, heapq in Python, top-k and merging sorted lists.

• Intermediate
• 17 min read
• 4 objectives

Before this lessonLesson 11: Balanced Trees: AVL, Red-Black and B-Trees

A normal queue serves items in arrival order. A priority queue serves the most important item first: the most urgent support ticket, the next timer to fire, the cheapest path to explore. You could keep a sorted list, but inserting into it costs O(n). A heap gives you O(log n) insert and O(log n) removal of the minimum, with O(1) peeking.

Heaps power task schedulers, Dijkstra's shortest path algorithm, event simulations and "top 10" leaderboards.

The heap property

A binary min-heap is a binary tree with two rules:

• Shape: every level is full except possibly the last, which fills left to right (a complete tree). So the height is always about log2 n.
• Order: every parent is less than or equal to its children. The smallest item is therefore always at the root.

Notice what is not required: siblings have no order, and a heap is not sorted. It is only "sorted enough" to find the minimum instantly. A max-heap flips the rule so the largest item sits on top.

Stored in a plain array

Because the tree is complete, it packs into an array with no pointers. For the node at index i: its children are at 2i + 1 and 2i + 2, and its parent is at (i - 1) // 2.

heap = [1, 3, 2, 7, 4, 5]
#          1
#        /   \
#       3     2
#      / \   /
#     7   4 5
for i, v in enumerate(heap):
    kids = [heap[c] for c in (2 * i + 1, 2 * i + 2) if c < len(heap)]
    print(f"index {i} value {v} children {kids}")

index 0 value 1 children [3, 2]
index 1 value 3 children [7, 4]
index 2 value 2 children [5]
index 3 value 7 children []
index 4 value 4 children []
index 5 value 5 children []

Push: add at the end, sift up

To insert, append the value at the end (keeping the shape) and then sift up: while it is smaller than its parent, swap them. It climbs at most the height of the tree, so push is O(log n).

Pop: move the last to the root, sift down

To remove the minimum, take the root, move the last element into its place, and sift down: swap it with its smaller child until neither child is smaller. Again at most log n swaps.

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 - 1) // 2] > a[i]:
            p = (i - 1) // 2
            a[p], a[i] = a[i], a[p]
            i = p

    def pop(self):
        a = self.a
        top = a[0]
        last = a.pop()
        if a:
            a[0] = last
            i = 0
            while True:
                l, r, small = 2 * i + 1, 2 * i + 2, i
                if l < len(a) and a[l] < a[small]:
                    small = l
                if r < len(a) and a[r] < a[small]:
                    small = r
                if small == i:
                    break
                a[i], a[small] = a[small], a[i]
                i = small
        return top

h = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
    h.push(x)
print(h.a)
print([h.pop() for _ in range(6)])

[1, 3, 2, 5, 9, 8]
[1, 2, 3, 5, 8, 9]

Popping everything returns values in sorted order. That is heapsort: n pops of O(log n) each gives O(n log n).

Python's heapq module

In practice use heapq, which runs these same algorithms on a regular list. It is a min-heap. heapify turns an existing list into a heap in O(n), which is faster than n separate pushes.

import heapq

nums = [5, 3, 8, 1, 9, 2]
heapq.heapify(nums)
print(nums[0])            # peek at the minimum
heapq.heappush(nums, 0)
print(heapq.heappop(nums), heapq.heappop(nums))

tasks = []
heapq.heappush(tasks, (2, "send newsletter"))
heapq.heappush(tasks, (1, "fix login bug"))
heapq.heappush(tasks, (3, "update docs"))
while tasks:
    priority, name = heapq.heappop(tasks)
    print(priority, name)

1
0 1
1 fix login bug
2 send newsletter
3 update docs

Tuples compare element by element, so (priority, item) makes a priority queue. There is no max-heap in heapq; the usual trick is to push negated numbers.

import heapq, itertools

counter = itertools.count()
pq = []
for prio, job in [(1, {"id": "a"}), (1, {"id": "b"}), (0, {"id": "c"})]:
    heapq.heappush(pq, (prio, next(counter), job))
print([heapq.heappop(pq)[2]["id"] for _ in range(3)])

# Max-heap by negating
scores = [40, 95, 70]
mx = [-s for s in scores]
heapq.heapify(mx)
print(-heapq.heappop(mx))

['c', 'a', 'b']
95

Top-k in O(n log k)

To find the k largest values in a huge stream, keep a min-heap of size k. Its root is the smallest of your current top k. Each new value bigger than the root replaces it. You never hold more than k items, so memory is O(k) and time is O(n log k). heapq.nlargest does this for you.

import heapq

def top_k(stream, k):
    heap = []
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

views = [120, 45, 980, 300, 15, 770, 410]
print(top_k(views, 3))
print(heapq.nlargest(3, views))

[980, 770, 410]
[980, 770, 410]

Merging k sorted lists

Put the first item of each list in a heap, pop the smallest, and push the next item from the same list. Each of the n total items goes through the heap once, costing O(n log k). This is how databases and external sort merge sorted runs; heapq.merge implements it lazily.

import heapq

a = [1, 4, 9]
b = [2, 3, 10]
c = [5, 6]
print(list(heapq.merge(a, b, c)))

[1, 2, 3, 4, 5, 6, 9, 10]

Complexity

Operation            Binary heap   Sorted list   Unsorted list
peek min             O(1)          O(1)          O(n)
push                 O(log n)      O(n)          O(1)
pop min              O(log n)      O(1)*         O(n)
build from n items   O(n)          O(n log n)    O(1)
search any value     O(n)          O(log n)      O(n)

* popping from the correct end of the list

The heap wins when you repeatedly mix inserts with "give me the smallest". If you need arbitrary lookups or sorted iteration, a balanced search tree is the better fit.

Recap

• A heap is a complete binary tree where each parent is no larger than its children.
• It lives in an array: children at 2i+1 and 2i+2, parent at (i-1)//2.
• Push sifts up and pop sifts down, both O(log n); peek is O(1) and heapify is O(n).
• heapq is a min-heap; use tuples for priorities, a counter for ties and negation for max-heaps.
• A size-k heap finds the top k of n items in O(n log k).

# Write your solution here