Python in a Nutshell, 2nd Edition

The heapq Module

The heapq module uses heap algorithms to keep a list in “nearly sorted” order as items are inserted and extracted. heapq’s operation is faster than either calling a list’s sort method after each insertion or using bisect, and, for many purposes, (such as implementing “priority queues”) the nearly sorted order supported by heapq may be just as useful as a fully sorted order. Module heapq supplies the following functions.

heapify	heapify(alist) Permutes alist as needed to make it satisfy the heap condition: for any i>=0, alist[i]<=alist[2*i+1] and alist[i]<=alist[2*i+2](if all the indices in question are <len(alist)). Note that if a list satisfies the heap condition, the list’s first item is the smallest (or equal-smallest) one. A sorted list satisfies the heap condition, but there are many other permutations of a list that satisfy the heap condition without requiring the list to be fully sorted. heapify runs in O(len(alist)) time.
heappop	heappop(alist) Removes and returns the smallest (first) item of alist, a list that satisfies the heap condition, and permutes some of the remaining items of alist to ensure the heap condition is still satisfied after the removal. heappop runs in O(len(alist)) time.
heappush	heappush(alist,item) Inserts the item in alist, a list that satisfies the heap condition, and permutes some items of alist to ensure the heap condition is still satisfied after the insertion. heappush runs in O(log(len(alist))) time.
heapreplace	heapreplace(alist,item ...