1616This module provides an implementation of the heap queue algorithm, also known
1717as the priority queue algorithm.
1818
19- Heaps are binary trees for which every parent node has a value less than or
20- equal to any of its children. We refer to this condition as the heap invariant.
19+ Min-heaps are binary trees for which every parent node has a value less than
20+ or equal to any of its children.
21+ We refer to this condition as the heap invariant.
2122
22- This implementation usesarrays for which
23- ``heap[k] <= heap[2*k+1] `` and ``heap[k] <= heap[2*k+2] `` for all *k *, counting
24- elements from zero .For the sake of comparison, non-existing elements are
25- considered to be infinite. The interesting property of a heap is that its
26- smallest element is always the root, ``heap[0] ``.
23+ For min-heaps, this implementation useslists for which
24+ ``heap[k] <= heap[2*k+1] `` and ``heap[k] <= heap[2*k+2] `` for all *k * for which
25+ the compared elements exist .Elements are counted from zero. The interesting
26+ property of amin- heap is that its smallest element is always the root,
27+ ``heap[0] ``.
2728
28- The API below differs from textbook heap algorithms in two aspects: (a) We use
29- zero-based indexing. This makes the relationship between the index for a node
30- and the indexes for its children slightly less obvious, but is more suitable
31- since Python uses zero-based indexing. (b) Our pop method returns the smallest
32- item, not the largest (called a "min heap" in textbooks; a "max heap" is more
33- common in texts because of its suitability for in-place sorting) .
29+ Max-heaps satisfy the reverse invariant: every parent node has a value
30+ * greater * than any of its children. These are implemented as lists for which
31+ `` maxheap[2*k+1] <= maxheap[k] `` and `` maxheap[2*k+2] <= maxheap[k] `` for all
32+ * k * for which the compared elements exist.
33+ The root, `` maxheap[0] ``, contains the* largest * element;
34+ `` heap.sort(reverse=True) `` maintains the max-heap invariant .
3435
35- These two make it possible to view the heap as a regular Python list without
36- surprises: ``heap[0] `` is the smallest item, and ``heap.sort() `` maintains the
37- heap invariant!
36+ The:mod: `!heapq ` API differs from textbook heap algorithms in two aspects: (a)
37+ We use zero-based indexing. This makes the relationship between the index for
38+ a node and the indexes for its children slightly less obvious, but is more
39+ suitable since Python uses zero-based indexing. (b) Textbooks often focus on
40+ max-heaps, due to their suitability for in-place sorting. Our implementation
41+ favors min-heaps as they better correspond to Python:class: `lists <list> `.
3842
39- To create a heap, use a list initialized to ``[] ``, or you can transform a
40- populated list into a heap via function:func: `heapify `.
43+ These two aspects make it possible to view the heap as a regular Python list
44+ without surprises: ``heap[0] `` is the smallest item, and ``heap.sort() ``
45+ maintains the heap invariant!
4146
42- The following functions are provided:
47+ Like:meth: `list.sort `, this implementation uses only the ``< `` operator
48+ for comparisons, for both min-heaps and max-heaps.
49+
50+ In the API below, and in this documentation, the unqualified term *heap *
51+ generally refers to a min-heap.
52+ The API for max-heaps is named using a ``_max `` suffix.
53+
54+ To create a heap, use a list initialized as ``[] ``, or transform an existing list
55+ into a min-heap or max-heap using the:func: `heapify ` or:func: `heapify_max `
56+ functions, respectively.
57+
58+ The following functions are provided for min-heaps:
4359
4460
4561..function ::heappush(heap, item)
4662
47- Push the value *item * onto the *heap *, maintaining the heap invariant.
63+ Push the value *item * onto the *heap *, maintaining themin- heap invariant.
4864
4965
5066..function ::heappop(heap)
5167
52- Pop and return the smallest item from the *heap *, maintaining the heap
68+ Pop and return the smallest item from the *heap *, maintaining themin- heap
5369 invariant. If the heap is empty,:exc: `IndexError ` is raised. To access the
5470 smallest item without popping it, use ``heap[0] ``.
5571
@@ -63,7 +79,7 @@ The following functions are provided:
6379
6480..function ::heapify(x)
6581
66- Transform list *x * into a heap, in-place, in linear time.
82+ Transform list *x * into amin- heap, in-place, in linear time.
6783
6884
6985..function ::heapreplace(heap, item)
@@ -82,6 +98,56 @@ The following functions are provided:
8298 on the heap.
8399
84100
101+ For max-heaps, the following functions are provided:
102+
103+
104+ ..function ::heapify_max(x)
105+
106+ Transform list *x * into a max-heap, in-place, in linear time.
107+
108+ ..versionadded ::next
109+
110+
111+ ..function ::heappush_max(heap, item)
112+
113+ Push the value *item * onto the max-heap *heap *, maintaining the max-heap
114+ invariant.
115+
116+ ..versionadded ::next
117+
118+
119+ ..function ::heappop_max(heap)
120+
121+ Pop and return the largest item from the max-heap *heap *, maintaining the
122+ max-heap invariant. If the max-heap is empty,:exc: `IndexError ` is raised.
123+ To access the largest item without popping it, use ``maxheap[0] ``.
124+
125+ ..versionadded ::next
126+
127+
128+ ..function ::heappushpop_max(heap, item)
129+
130+ Push *item * on the max-heap *heap *, then pop and return the largest item
131+ from *heap *.
132+ The combined action runs more efficiently than:func: `heappush_max `
133+ followed by a separate call to:func: `heappop_max `.
134+
135+ ..versionadded ::next
136+
137+
138+ ..function ::heapreplace_max(heap, item)
139+
140+ Pop and return the largest item from the max-heap *heap * and also push the
141+ new *item *.
142+ The max-heap size doesn't change. If the max-heap is empty,
143+ :exc: `IndexError ` is raised.
144+
145+ The value returned may be smaller than the *item * added. Refer to the
146+ analogous function:func: `heapreplace ` for detailed usage notes.
147+
148+ ..versionadded ::next
149+
150+
85151The module also offers three general purpose functions based on heaps.
86152
87153