[docs] Bug in example 8.4.2

Stoney Jackson dr.stoney at gmail.com
Wed Sep 7 01:50:38 CEST 2011


Hi,

In the example of 8.4.2 at http://docs.python.org/library/heapq.html
the following line should be inside the if-statement:

        del task_finder[task]

Consider the following scenario:

>>> import itertools
>>> from heapq import *
>>> 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)
...     entry = [priority, count, task]
...     task_finder[task] = entry
...     heappush(pq, entry)
... 
>>> def get_top_priority():
...     while True:
...         priority, count, task = heappop(pq)
...         del task_finder[task]
...         if count is not INVALID:
...             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
... 
>>> add_task(1, 'a')
>>> add_task(2, 'b')
>>> reprioritize(3, 'a')
>>> pq
[[1, 0, 'a'], [2, 2, 'b'], [3, 1, 'a']]
>>> get_top_priority()
'b'
>>> pq
[[3, 1, 'a']]
>>> reprioritize(4,'a')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in reprioritize
KeyError: 'a'
>>> 

Regards,
Stoney


More information about the docs mailing list