https://github.com/python/cpython/commit/14cdb0d7a590052df2a3d811b6d951387f81a11c commit: 14cdb0d7a590052df2a3d811b6d951387f81a11c branch: 3.12 author: Miss Islington (bot) <[email protected]> committer: hauntsaninja <[email protected]> date: 2024-04-13T07:11:49Z summary:
[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 <[email protected]> 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]
