[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