From 57410c12e8918df68c1cfac63c702cb1eac25960 Mon Sep 17 00:00:00 2001 From: Georg Brandl Date: Tue, 23 Nov 2010 08:37:54 +0000 Subject: #10511: clarification of what heaps are; suggested by Johannes Hoff. --- Doc/library/heapq.rst | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst index 67bda56..f6b14ca 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 ` -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 -- cgit v0.12