8.8. 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)
Logically equivalent to heappop followed by heappush, similar to:
def heapreplace(alist, item):
try: return heappop(alist)
finally: heappush(alist, item)
heapreplace runs in O(log(len(alist))) time and is generally faster than the logically equivalent function just shown.
| nlargest | nlargest(n,seq)
Returns a reverse-sorted list with the n largest items of iterable seq (less than n if seq has less than n items); like sorted(seq, reverse=True)[:n] but faster. In Python 2.5, you may also specify a key= argument, like you can for sorted.
| nsmallest | nsmallest(n,seq)
Returns a sorted list with the n smallest items of iterable seq (less than n if seq has less than n items); like sorted(seq)[:n] but faster. In Python 2.5, you may also specify a key= argument, like you can for sorted.
|
![](images/pixel.jpg) |