The heap: the smallest always at hand

Sometimes you want to keep taking the smallest of a pile of numbers while adding new ones in between. Sorting the list again every time is costly, and so is searching for min every time. A heap is for exactly this: both adding and taking out the smallest finish in log n steps.

1import heapq
2heap = []
3for v in [5, 1, 8, 3]:
4    heapq.heappush(heap, v)
5first = heapq.heappop(heap)   # 1
6second = heapq.heappop(heap)  # 3
7smallest_left = heap[0]       # 5

In Python a heap is an ordinary list; what makes it a heap is the heapq functions. heappush adds, heappop takes out the smallest, heap[0] looks at the smallest without removing it. To turn a list you already have into a heap in one go there is heapq.heapify(values).

Put n numbers on a heap and take them out one by one and they come out sorted; n pushes and n pops at log n each: n log n in all. So sorting with a heap is in the same class as a good sort. The heap's real gain shows when you do not need all of the sorted order.

Tasks