Heap#
heapq provides a binary min-heap on top of a list. Use
for priority queues and top-N extraction. The list itself is the
heap; heapq is a module of free functions that operate on it.
import heapq
xs = [5, 1, 9, 3, 7]
heapq.heapify(xs) # O(n)
heapq.heappush(xs, 4) # O(log n)
heapq.heappop(xs) # O(log n), returns smallest
smallest_3 = heapq.nsmallest(3, items)
largest_3 = heapq.nlargest(3, items, key=lambda x: x.score)
For a max-heap, push negated keys (heapq only has min). For
heap entries with payloads, push tuples of (priority,
sequence, item); the sequence breaks ties without requiring
item to be orderable.
import itertools
counter = itertools.count()
heap = []
heapq.heappush(heap, (priority, next(counter), task))
heapq.merge lazily merges multiple sorted iterables.
for x in heapq.merge(sorted_a, sorted_b, sorted_c):
...