python · encukou · May 5, 2025 · Mar 1, 2025 · Mar 1, 2025 · Mar 1, 2025
@@ -16,40 +16,56 @@
 This module provides an implementation of the heap queue algorithm, also known
 as the priority queue algorithm.
 
-Heaps are binary trees for which every parent node has a value less than or
-equal to any of its children.  We refer to this condition as the heap invariant.
+Min-heaps are binary trees for which every parent node has a value less than
+or equal to any of its children.
+We refer to this condition as the heap invariant.
 
-This implementation uses arrays for which
-``heap[k] <= heap[2*k+1]`` and ``heap[k] <= heap[2*k+2]`` for all *k*, counting
-elements from zero.  For the sake of comparison, non-existing elements are
-considered to be infinite.  The interesting property of a heap is that its
-smallest element is always the root, ``heap[0]``.
+For min-heaps, this implementation uses lists for which
+``heap[k] <= heap[2*k+1]`` and ``heap[k] <= heap[2*k+2]`` for all *k* for which
+the compared elements exist.  Elements are counted from zero.  The interesting
+property of a min-heap is that its smallest element is always the root,
+``heap[0]``.
 
-The API below differs from textbook heap algorithms in two aspects: (a) We use
-zero-based 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 zero-based indexing. (b) Our pop method returns the smallest
-item, not the largest (called a "min heap" in textbooks; a "max heap" is more
-common in texts because of its suitability for in-place sorting).
+Max-heaps satisfy the reverse invariant: every parent node has a value
+*greater* than any of its children.  These are implemented as lists for which
+``maxheap[2*k+1] <= maxheap[k]`` and ``maxheap[2*k+2] <= maxheap[k]`` for all
+*k* for which the compared elements exist.
+The root, ``maxheap[0]``, contains the *largest* element;
+``heap.sort(reverse=True)`` maintains the max-heap invariant.
 
-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!
+The :mod:`!heapq` API differs from textbook heap algorithms in two aspects: (a)
+We use zero-based 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 zero-based indexing. (b) Textbooks often focus on
+max-heaps, due to their suitability for in-place sorting. Our implementation
+favors min-heaps as they better correspond to Python :class:`lists <list>`.
 
-To create a heap, use a list initialized to ``[]``, or you can transform a
-populated list into a heap via function :func:`heapify`.
+These two aspects 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!
 
-The following functions are provided:
+Like :meth:`list.sort`, this implementation uses only the ``<`` operator
+for comparisons, for both min-heaps and max-heaps.
+
+In the API below, and in this documentation, the unqualified term *heap*
+generally refers to a min-heap.
+The API for max-heaps is named using a ``_max``  suffix.
+
+To create a heap, use a list initialized as ``[]``, or transform an existing list
+into a min-heap or max-heap using the :func:`heapify` or :func:`heapify_max`
+functions, respectively.
+
+The following functions are provided for min-heaps:
 
 
 .. function:: heappush(heap, item)
 
-   Push the value *item* onto the *heap*, maintaining the heap invariant.
+   Push the value *item* onto the *heap*, maintaining the min-heap invariant.
 
 
 .. function:: heappop(heap)
 
-   Pop and return the smallest item from the *heap*, maintaining the heap
+   Pop and return the smallest item from the *heap*, maintaining the min-heap
    invariant.  If the heap is empty, :exc:`IndexError` is raised.  To access the
    smallest item without popping it, use ``heap[0]``.
 
@@ -63,7 +79,7 @@ The following functions are provided:
 
 .. function:: heapify(x)
 
-   Transform list *x* into a heap, in-place, in linear time.
+   Transform list *x* into a min-heap, in-place, in linear time.
 
 
 .. function:: heapreplace(heap, item)
@@ -82,6 +98,56 @@ The following functions are provided:
    on the heap.
 
 
+For max-heaps, the following functions are provided:
+
+
+.. function:: heapify_max(x)
+
+   Transform list *x* into a max-heap, in-place, in linear time.
+
+   .. versionadded:: next
+
+
+.. function:: heappush_max(heap, item)
+
+   Push the value *item* onto the max-heap *heap*, maintaining the max-heap
+   invariant.
+
+   .. versionadded:: next
+
+
+.. function:: heappop_max(heap)
+
+   Pop and return the largest item from the max-heap *heap*, maintaining the
+   max-heap invariant.  If the max-heap is empty, :exc:`IndexError` is raised.
+   To access the largest item without popping it, use ``maxheap[0]``.
+
+   .. versionadded:: next
+
+
+.. function:: heappushpop_max(heap, item)
+
+   Push *item* on the max-heap *heap*, then pop and return the largest item
+   from *heap*.
+   The combined action runs more efficiently than :func:`heappush_max`
+   followed by a separate call to :func:`heappop_max`.
+
+   .. versionadded:: next
+
+
+.. function:: heapreplace_max(heap, item)
+
+   Pop and return the largest item from the max-heap *heap* and also push the
+   new *item*.
+   The max-heap size doesn't change. If the max-heap is empty,
+   :exc:`IndexError` is raised.
+
+   The value returned may be smaller than the *item* added.  Refer to the
+   analogous function :func:`heapreplace` for detailed usage notes.
+
+   .. versionadded:: next
+
+
 The module also offers three general purpose functions based on heaps.
 
 

diff --git a/Doc/whatsnew/3.14.rst b/Doc/whatsnew/3.14.rst
@@ -844,6 +844,18 @@ graphlib
   (Contributed by Daniel Pope in :gh:`130914`)
 
 
+heapq
+-----
+
+* Add functions for working with max-heaps:
+
+  * :func:`heapq.heapify_max`,
+  * :func:`heapq.heappush_max`,
+  * :func:`heapq.heappop_max`,
+  * :func:`heapq.heapreplace_max`
+  * :func:`heapq.heappushpop_max`
+
+
 hmac
 ----
 

@@ -178,7 +178,7 @@ def heapify(x):
     for i in reversed(range(n//2)):
         _siftup(x, i)
 
-def _heappop_max(heap):
+def heappop_max(heap):
     """Maxheap version of a heappop."""
     lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
     if heap:
@@ -188,19 +188,32 @@ def _heappop_max(heap):
         return returnitem
     return lastelt
 
-def _heapreplace_max(heap, item):
+def heapreplace_max(heap, item):
     """Maxheap version of a heappop followed by a heappush."""
     returnitem = heap[0]    # raises appropriate IndexError if heap is empty
     heap[0] = item
     _siftup_max(heap, 0)
     return returnitem
 
-def _heapify_max(x):
+def heappush_max(heap, item):
+    """Maxheap version of a heappush."""
+    heap.append(item)
+    _siftdown_max(heap, 0, len(heap)-1)
+
+def heappushpop_max(heap, item):
+    """Maxheap fast version of a heappush followed by a heappop."""
+    if heap and item < heap[0]:
+        item, heap[0] = heap[0], item
+        _siftup_max(heap, 0)
+    return item
+
+def heapify_max(x):
     """Transform list into a maxheap, in-place, in O(len(x)) time."""
     n = len(x)
     for i in reversed(range(n//2)):
         _siftup_max(x, i)
 
+
 # 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
 # is the index of a leaf with a possibly out-of-order value.  Restore the
 # heap invariant.
@@ -335,9 +348,9 @@ def merge(*iterables, key=None, reverse=False):
     h_append = h.append
 
     if reverse:
-        _heapify = _heapify_max
-        _heappop = _heappop_max
-        _heapreplace = _heapreplace_max
+        _heapify = heapify_max
+        _heappop = heappop_max
+        _heapreplace = heapreplace_max
         direction = -1
     else:
         _heapify = heapify
@@ -490,10 +503,10 @@ def nsmallest(n, iterable, key=None):
         result = [(elem, i) for i, elem in zip(range(n), it)]
         if not result:
             return result
-        _heapify_max(result)
+        heapify_max(result)
         top = result[0][0]
         order = n
-        _heapreplace = _heapreplace_max
+        _heapreplace = heapreplace_max
         for elem in it:
             if elem < top:
                 _heapreplace(result, (elem, order))
@@ -507,10 +520,10 @@ def nsmallest(n, iterable, key=None):
     result = [(key(elem), i, elem) for i, elem in zip(range(n), it)]
     if not result:
         return result
-    _heapify_max(result)
+    heapify_max(result)
     top = result[0][0]
     order = n
-    _heapreplace = _heapreplace_max
+    _heapreplace = heapreplace_max
     for elem in it:
         k = key(elem)
         if k < top:
@@ -583,19 +596,13 @@ def nlargest(n, iterable, key=None):
     from _heapq import *
 except ImportError:
     pass
-try:
-    from _heapq import _heapreplace_max
-except ImportError:
-    pass
-try:
-    from _heapq import _heapify_max
-except ImportError:
-    pass
-try:
-    from _heapq import _heappop_max
-except ImportError:
-    pass
 
+# For backwards compatibility
+_heappop_max  = heappop_max
+_heapreplace_max = heapreplace_max
+_heappush_max = heappush_max
+_heappushpop_max = heappushpop_max
+_heapify_max = heapify_max
 
 if __name__ == "__main__":