https://github.com/python/cpython/commit/37a4cbd8727fe392dd5c78aea60a7c37fdbad89a
commit: 37a4cbd8727fe392dd5c78aea60a7c37fdbad89a
branch: main
author: Shantanu <[email protected]>
committer: hauntsaninja <[email protected]>
date: 2024-04-13T00:05:27-07:00
summary:
gh-114466: explicitly define heap invariant (#117778)
I think the choice of wording in these docs is great and doesn't
need to change. However, it could be useful to explicitly define
this term / the cost of doing so seems relatively low.
files:
M Doc/library/heapq.rst
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst
index ddbada13bddf5b..ad407141a2f590 100644
--- a/Doc/library/heapq.rst
+++ b/Doc/library/heapq.rst
@@ -17,7 +17,9 @@ 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. This implementation uses arrays for which
+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
@@ -319,4 +321,3 @@ applications, and I think it is good to keep a 'heap'
module around. :-)
backwards, and this was also used to avoid the rewinding time. Believe me,
real
good tape sorts were quite spectacular to watch! From all times, sorting has
always been a Great Art! :-)
-
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/python-checkins.python.org/
Member address: [email protected]
