diff options
| author | Shantanu <12621235+hauntsaninja@users.noreply.github.com> | 2024-04-13 07:05:27 (GMT) |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-04-13 07:05:27 (GMT) |
| commit | 37a4cbd8727fe392dd5c78aea60a7c37fdbad89a (patch) | |
| tree | 8fce4055293f65da26615592d13bdbca11c0c642 | |
| parent | c2a551a30b520e520b084eec251f168549e1a3f0 (diff) | |
| download | cpython-37a4cbd8727fe392dd5c78aea60a7c37fdbad89a.zip cpython-37a4cbd8727fe392dd5c78aea60a7c37fdbad89a.tar.gz cpython-37a4cbd8727fe392dd5c78aea60a7c37fdbad89a.tar.bz2 | |
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.
| -rw-r--r-- | Doc/library/heapq.rst | 5 |
1 files changed, 3 insertions, 2 deletions
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst index ddbada1..ad40714 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! :-) - |