AI Hints
DSA in Python · Lesson 71 of 132

heapq in Python

Priority queues made easy.

⏱ 2 min read▶ Video at 1:23:30🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Python's heap Q module turns an ordinary list into a heap. There's no special class. Just a handful of functions that keep the list in heap order.

heapq in Python
From the video: heapq in Python
  • heapq module
  • An ordinary list
  • A few functions

An emergency room

Each patient is a tuple, of urgency and the problem. Smaller numbers are more urgent. Heap push adds a patient, and heap pop always removes the most urgent one, whatever order they arrived in. Run it. Urgency one is treated first, then two, then three.

er.pypython
import heapq

waiting = []
heapq.heappush(waiting, (3, "sprained ankle"))
heapq.heappush(waiting, (1, "heart attack"))
heapq.heappush(waiting, (2, "broken arm"))
heapq.heappush(waiting, (3, "cold"))

while waiting:
    urgency, problem = heapq.heappop(waiting)
    print(urgency, problem)
Output
1 heart attack
2 broken arm
3 cold
3 sprained ankle

heapq tips

Heapify turns an existing list into a heap in O of N. The smallest item is always at index zero. Heap Q is a min heap. For a max heap, store negative numbers. And tuples compare item by item, so the first value decides the priority, and the second breaks ties.

keyvalue
heappush / heappopO(log n)
heapify(list)O(n)
heap[0]peek the smallest
Max heappush -value

Summary

Heap Q gives you a priority queue on a plain list. Push and pop in O of log N, and the smallest is always at index zero. Next, a classic heap problem. The top K items.

Key takeaways
  • heappush
  • heappop
  • heap[0] is the smallest
Next up: Practice: Top K — the biggest few