diff options
| author | Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> | 2024-04-13 07:11:49 (GMT) |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-04-13 07:11:49 (GMT) |
| commit | 14cdb0d7a590052df2a3d811b6d951387f81a11c (patch) | |
| tree | cdf16b5cb24b97968bf9ac5c15b7d237da8dc5f8 /Doc/library/heapq.rst | |
| parent | 0b11f0ef4f29cb9686c1cc4339260e7b83d01729 (diff) | |
| download | cpython-14cdb0d7a590052df2a3d811b6d951387f81a11c.zip cpython-14cdb0d7a590052df2a3d811b6d951387f81a11c.tar.gz cpython-14cdb0d7a590052df2a3d811b6d951387f81a11c.tar.bz2 | |
[3.12] gh-114466: explicitly define heap invariant (GH-117778) (#117835)
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.
(cherry picked from commit 37a4cbd8727fe392dd5c78aea60a7c37fdbad89a)
Co-authored-by: Shantanu <12621235+hauntsaninja@users.noreply.github.com>
Diffstat (limited to 'Doc/library/heapq.rst')
| -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! :-) - |