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.

 Min-heaps (resp. max-heaps) are binary trees for which every parent node
 has a value less than (resp. greater than) or equal to any of its children.
 We refer to this condition as the heap invariant. Unless stated otherwise,
 *heaps* refer to min-heaps.

 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]``.

 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).
 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.

 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]``.

 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!

 Max-heaps satisfy the reverse invariant: every parent node 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.

 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 lists: :meth:`list.sort`
 maintains the *min*-heap invariant.

 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 unqalified term *heap*
 generally refers to a min-heap.
 API for max-heaps is named using a ``_max``  suffix.

 To create a heap, use a list initialized to ``[]``, or you can transform a
 populated list into a heap via function :func:`heapify`.

 The following functions are provided:
 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)

 .. function:: heappush_max(heap, item)

   Push the value *item* onto the max-heap *heap*, maintaining the heap invariant.
   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 heap
   invariant.  If the max-heap is empty, :exc:`IndexError` is raised.  To access the
   largest item without popping it, use ``heap[0]``.
   Pop and return the largest item from the max-heap *heap*, maintaining the
 max-heapinvariant.  If the max-heap is empty, :exc:`IndexError` is raised.
 To access thelargest 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*.
   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`.


 .. 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.
   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.
   The value returned may be smaller than the *item* added.  Refer to the
 analogousfunction :func:`heapreplace` for detailed usage notes.

   .. versionadded:: next
Original file line number	Diff line number	Diff line change
Expand Up		@@ -16,42 +16,56 @@
		This module provides an implementation of the heap queue algorithm, also known
		as the priority queue algorithm.

		Min-heaps (resp. max-heaps) are binary trees for which every parent node
		has a value less than (resp. greater than) or equal to any of its children.
		We refer to this condition as the heap invariant. Unless stated otherwise,
		heaps refer to min-heaps.

		This implementation uses arrays 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 interesting property of a 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).
		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.

		For min-heaps, this implementation uses lists 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 a min-heap is that its smallest element is always the root,
		``heap[0]``.

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

		Max-heaps satisfy the reverse invariant: every parent node node has a value
StanFromIreland marked this conversation as resolved. OutdatedShow resolvedHide resolved
		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]``, contains the largest element;
		``heap.sort(reverse=True)`` maintains the max-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 lists: :meth:`list.sort`
		maintains the min-heap invariant.
StanFromIreland marked this conversation as resolved. OutdatedShow resolvedHide resolved

		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 unqalified term heap
		generally refers to a min-heap.
		API for max-heaps is named using a ``_max`` suffix.

		To create a heap, use a list initialized to ``[]``, or you can transform a
		populated list into a heap via function :func:`heapify`.

		The following functions are provided:
		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		@@ -65,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 DownExpand Up		@@ -96,23 +110,25 @@ For max-heaps, the following functions are provided:

		.. 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 heap invariant.
		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 heap
		invariant. If the max-heap is empty, :exc:`IndexError` is raised. To access the
		largest item without popping it, use ``heap[0]``.
		Pop and return the largest item from the max-heap heap, maintaining the
		max-heapinvariant. If the max-heap is empty, :exc:`IndexError` is raised.
		To access thelargest 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.
		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`.

Expand All		@@ -121,11 +137,13 @@ For max-heaps, the following functions are provided:

		.. 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.
		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.
		The value returned may be smaller than the item added. Refer to the
		analogousfunction :func:`heapreplace` for detailed usage notes.

		.. versionadded:: next

Expand Down