diff options
| author | Georg Brandl <georg@python.org> | 2010-11-23 08:37:54 +0000 |
|---|---|---|
| committer | Georg Brandl <georg@python.org> | 2010-11-23 08:37:54 +0000 |
| commit | 57410c12e8918df68c1cfac63c702cb1eac25960 (patch) | |
| tree | b36c36560c61b2e03ea48db37fa708a97d79cd18 /Doc/library/heapq.rst | |
| parent | 5a9326502d3e728158116940212eb08198f53ee8 (diff) | |
| download | cpython-git-57410c12e8918df68c1cfac63c702cb1eac25960.tar.gz | |
#10511: clarification of what heaps are; suggested by Johannes Hoff.
Diffstat (limited to 'Doc/library/heapq.rst')
| -rw-r--r-- | Doc/library/heapq.rst | 11 |
1 files changed, 6 insertions, 5 deletions
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst index 67bda5698d..f6b14ca6d9 100644 --- a/Doc/library/heapq.rst +++ b/Doc/library/heapq.rst @@ -16,11 +16,12 @@ as the priority queue algorithm. Latest version of the :source:`heapq Python source code <Lib/heapq.py>` -Heaps are 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 ``heap[0]`` is always its smallest -element. +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 +``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 |