May 5, 2025 · Mar 1, 2025 · Mar 1, 2025 · Mar 1, 2025 · Mar 1, 2025 · Mar 1, 2025
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst
 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.

 Thisimplementation usesarrays 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 interestingproperty of a heap is that its
 smallest element is always the root,``heap[0]``.
 For min-heaps, thisimplementation useslists 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 amin-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, notthe 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]``, containsthe*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 themin-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 themin-heap
   invariant.  If the heap is empty, :exc:`IndexError` is raised.  To access the
   smallest item without popping it, use ``heap[0]``.


 .. function:: heapify(x)

   Transform list *x* into a heap, in-place, in linear time.
   Transform list *x* into amin-heap, in-place, in linear time.


 .. function:: heapreplace(heap, item)
   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
  (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
 ----

diff --git a/Lib/heapq.py b/Lib/heapq.py
    for i in reversed(range(n//2)):
        _siftup(x, i)

 def_heappop_max(heap):
 defheappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        return returnitem
    return lastelt

 def_heapreplace_max(heap, item):
 defheapreplace_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.
    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
        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))
    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:
    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__":
Original file line number	Diff line number	Diff line change
Expand Up		@@ -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.

		Thisimplementation usesarrays for which
		``heap[k] <= heap[2k+1]`` and ``heap[k] <= heap[2k+2]`` for all k, counting
		elements from zero.For the sake of comparison, non-existing elements are
		considered to be infinite. The interestingproperty of a heap is that its
		smallest element is always the root,``heap[0]``.
		For min-heaps, thisimplementation useslists for which
		``heap[k] <= heap[2k+1]`` and ``heap[k] <= heap[2k+2]`` for all k for which
		the compared elements exist.Elements are counted from zero. The interesting
		property of amin-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, notthe 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[2k+1] <= maxheap[k]`` and ``maxheap[2k+2] <= maxheap[k]`` for all
		k for which the compared elements exist.
		The root, ``maxheap[0]``, containsthelargest 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 themin-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 themin-heap
		invariant. If the heap is empty, :exc:`IndexError` is raised. To access the
		smallest item without popping it, use ``heap[0]``.

Expand All		@@ -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 amin-heap, in-place, in linear time.


		.. function:: heapreplace(heap, item)
Expand All		@@ -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)
StanFromIreland marked this conversation as resolved. Show resolvedHide resolved

		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)
StanFromIreland marked this conversation as resolved. Show resolvedHide resolved

		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.


Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -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
		----

Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -178,7 +178,7 @@ def heapify(x):
		for i in reversed(range(n//2)):
		_siftup(x, i)

		def_heappop_max(heap):
		defheappop_max(heap):
		"""Maxheap version of a heappop."""
		lastelt = heap.pop() # raises appropriate IndexError if heap is empty
		if heap:
Expand All		@@ -188,19 +188,32 @@ def _heappop_max(heap):
		return returnitem
		return lastelt

		def_heapreplace_max(heap, item):
		defheapreplace_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):
StanFromIreland marked this conversation as resolved. Show resolvedHide resolved
		"""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.
Expand DownExpand Up		@@ -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
Expand DownExpand Up		@@ -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))
Expand All		@@ -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:
Expand DownExpand Up		@@ -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
picnixz marked this conversation as resolved. Show resolvedHide resolved

		# 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__":

Expand Down