From 3e0a3faaa2ab756d6b28cc25b7e3f95bb45f800f Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sun, 9 Oct 2011 17:32:43 +0100
Subject: [PATCH] Clean-up and improve the priority queue example in the heapq
 docs.

---
 Doc/library/heapq.rst | 50 +++++++++++++++++++++----------------------
 1 file changed, 25 insertions(+), 25 deletions(-)

diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst
index c995802bbd..f0723b7b27 100644
--- a/Doc/library/heapq.rst
+++ b/Doc/library/heapq.rst
@@ -187,36 +187,36 @@ changes to its priority or removing it entirely.  Finding a task can be done
 with a dictionary pointing to an entry in the queue.
 
 Removing the entry or changing its priority is more difficult because it would
-break the heap structure invariants.  So, a possible solution is to mark an
-entry as invalid and optionally add a new entry with the revised priority::
-
-    pq = []                         # the priority queue list
-    counter = itertools.count(1)    # unique sequence count
-    task_finder = {}                # mapping of tasks to entries
-    INVALID = 0                     # mark an entry as deleted
-
-    def add_task(priority, task, count=None):
-        if count is None:
-            count = next(counter)
+break the heap structure invariants.  So, a possible solution is to mark the
+existing entry as removed and add a new entry with the revised priority::
+
+    pq = []                         # list of entries arranged in a heap
+    entry_finder = {}               # mapping of tasks to entries
+    REMOVED = '<removed-task>'      # placeholder for a removed task
+    counter = itertools.count()     # unique sequence count
+
+    def add_task(task, priority=0):
+        'Add a new task or update the priority of an existing task'
+        if task in entry_finder:
+            remove_task(task)
+        count = next(counter)
         entry = [priority, count, task]
-        task_finder[task] = entry
+        entry_finder[task] = entry
         heappush(pq, entry)
 
-    def get_top_priority():
-        while True:
+    def remove_task(task):
+        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
+        entry = entry_finder.pop(task)
+        entry[-1] = REMOVED
+
+    def pop_task():
+        'Remove and return the lowest priority task. Raise KeyError if empty.'
+        while pq:
             priority, count, task = heappop(pq)
-            if count is not INVALID:
-                del task_finder[task]
+            if task is not REMOVED:
+                del entry_finder[task]
                 return task
-
-    def delete_task(task):
-        entry = task_finder[task]
-        entry[1] = INVALID
-
-    def reprioritize(priority, task):
-        entry = task_finder[task]
-        add_task(priority, task, entry[1])
-        entry[1] = INVALID
+        raise KeyError('pop from an empty priority queue')
 
 
 Theory
-- 
2.40.0