| 1 | # -*- coding: Latin-1 -*- |
| 2 | |
| 3 | """Heap queue algorithm (a.k.a. priority queue). |
| 4 | |
| 5 | Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for |
| 6 | all k, counting elements from 0. For the sake of comparison, |
| 7 | non-existing elements are considered to be infinite. The interesting |
| 8 | property of a heap is that a[0] is always its smallest element. |
| 9 | |
| 10 | Usage: |
| 11 | |
| 12 | heap = [] # creates an empty heap |
| 13 | heappush(heap, item) # pushes a new item on the heap |
| 14 | item = heappop(heap) # pops the smallest item from the heap |
| 15 | item = heap[0] # smallest item on the heap without popping it |
| 16 | heapify(x) # transforms list into a heap, in-place, in linear time |
| 17 | item = heapreplace(heap, item) # pops and returns smallest item, and adds |
| 18 | # new item; the heap size is unchanged |
| 19 | |
| 20 | Our API differs from textbook heap algorithms as follows: |
| 21 | |
| 22 | - We use 0-based indexing. This makes the relationship between the |
| 23 | index for a node and the indexes for its children slightly less |
| 24 | obvious, but is more suitable since Python uses 0-based indexing. |
| 25 | |
| 26 | - Our heappop() method returns the smallest item, not the largest. |
| 27 | |
| 28 | These two make it possible to view the heap as a regular Python list |
| 29 | without surprises: heap[0] is the smallest item, and heap.sort() |
| 30 | maintains the heap invariant! |
| 31 | """ |
| 32 | |
| 33 | # Original code by Kevin O'Connor, augmented by Tim Peters and Raymond Hettinger |
| 34 | |
| 35 | __about__ = """Heap queues |
| 36 | |
| 37 |