From 62abc2f6ce9cb2ad9a83f744cf91cdf77a769f24 Mon Sep 17 00:00:00 2001
From: Tim Peters <tim.peters@gmail.com>
Date: Fri, 2 Aug 2002 20:09:14 +0000
Subject: heappop():  Added comments; simplified and sped the code.

---
 Lib/heapq.py | 40 +++++++++++++++++++---------------------
 1 file changed, 19 insertions(+), 21 deletions(-)

diff --git a/Lib/heapq.py b/Lib/heapq.py
index 524f65c..91dc81b 100644
--- a/Lib/heapq.py
+++ b/Lib/heapq.py
@@ -142,27 +142,25 @@ def heappop(heap):
     returnitem = heap[0]
     item = heap.pop()
     pos = 0
-    while True:
-        child2pos = (pos + 1) * 2
-        child1pos = child2pos - 1
-        if child2pos < endpos:
-            child1 = heap[child1pos]
-            child2 = heap[child2pos]
-            if item <= child1 and item <= child2:
-                break
-            if child1 < child2:
-                heap[pos] = child1
-                pos = child1pos
-                continue
-            heap[pos] = child2
-            pos = child2pos
-            continue
-        if child1pos < endpos:
-            child1 = heap[child1pos]
-            if child1 < item:
-                heap[pos] = child1
-                pos = child1pos
-        break
+    # Sift item into position, down from the root, moving the smaller
+    # child up, until finding pos such that item <= pos's children.
+    childpos = 2*pos + 1    # leftmost child position
+    while childpos < endpos:
+        # Set childpos and child to reflect smaller child.
+        child = heap[childpos]
+        rightpos = childpos + 1
+        if rightpos < endpos:
+            rightchild = heap[rightpos]
+            if rightchild < child:
+                childpos = rightpos
+                child = rightchild
+        # If item is no larger than smaller child, we're done, else
+        # move the smaller child up.
+        if item <= child:
+            break
+        heap[pos] = child
+        pos = childpos
+        childpos = 2*pos + 1
     heap[pos] = item
     return returnitem
 
-- 
cgit v0.12