Section 8.8. The heapq Module


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.





Python in a Nutshell
Python in a Nutshell, Second Edition (In a Nutshell)
ISBN: 0596100469
EAN: 2147483647
Year: 2004
Pages: 192
Authors: Alex Martelli

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net