EmbeddedPkg: Extend NvVarStoreFormattedLib LIBRARY_CLASS

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.2 / Lib / heapq.py

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