Module heapq
Heap queue algorithm (a.k.a. priority queue).
Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for
all k, counting elements from 0. For the sake of comparison,
nonexisting elements are considered to be infinite. The interesting
property of a heap is that a[0] is always its smallest element.
Usage:
heap = [] # creates an empty heap
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
item = heap[0] # smallest item on the heap without popping it
heapify(x) # transforms list into a heap, inplace, in linear time
item = heapreplace(heap, item) # pops and returns smallest item, and adds
# new item; the heap size is unchanged
Our API differs from textbook heap algorithms as follows:
 We use 0based indexing. This makes the relationship between the
index for a node and the indexes for its children slightly less
obvious, but is more suitable since Python uses 0based indexing.
 Our heappop() method returns the smallest item, not the largest.
These two make it possible to view the heap as a regular Python list
without surprises: heap[0] is the smallest item, and heap.sort()
maintains the heap invariant!

_siftdown(heap,
startpos,
pos) 





heappush(...)
Push item onto heap, maintaining the heap invariant. 



heappop(...)
Pop the smallest item off the heap, maintaining the heap invariant. 



heapify(...)
Transform list into a heap, inplace, in O(len(heap)) time. 



heapreplace(...)
Pop and return the current smallest value, and add the new item. 



nsmallest(n,
iterable,
key=None)
Find the n smallest elements in a dataset. 



nlargest(n,
iterable,
key=None)
Find the n largest elements in a dataset. 



__about__ = ' Heap queues\n\n[explanation by Fran\xe7ois Pinard ...

Imports:
islice,
repeat,
count,
imap,
izip,
tee,
itemgetter,
bisect,
_nsmallest,
_nlargest
Pop and return the current smallest value, and add the new item.
This is more efficient than heappop() followed by heappush(), and can be
more appropriate when using a fixedsize heap. Note that the value
returned may be larger than item! That constrains reasonable uses of
this routine unless written as part of a conditional replacement:
if item > heap[0]:
item = heapreplace(heap, item)

nsmallest(n,
iterable,
key=None)


Find the n smallest elements in a dataset.
Equivalent to: sorted(iterable, key=key)[:n]

nlargest(n,
iterable,
key=None)


Find the n largest elements in a dataset.
Equivalent to: sorted(iterable, key=key, reverse=True)[:n]

__about__
 Value:
''' Heap queues
[explanation by Fran\xe7ois Pinard]
Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for
all k, counting elements from 0. For the sake of comparison,
nonexisting elements are considered to be infinite. The interesting
property of a heap is that a[0] is always its smallest element.
...

