Commit | Line | Data |
---|---|---|
920dae64 AT |
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 |