diff options
author | Raymond Hettinger <python@rcn.com> | 2010-08-07 23:31:27 (GMT) |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2010-08-07 23:31:27 (GMT) |
commit | 0e833c3227271a0295edc945693090a5f1daad7d (patch) | |
tree | 8ee808b396f18c4b3ab90e50be44fa7457537221 | |
parent | fa45076cbd1581b606ca9d51b735ef6c58f901cf (diff) | |
download | cpython-0e833c3227271a0295edc945693090a5f1daad7d.zip cpython-0e833c3227271a0295edc945693090a5f1daad7d.tar.gz cpython-0e833c3227271a0295edc945693090a5f1daad7d.tar.bz2 |
Document implementation notes for priority queues
-rw-r--r-- | Doc/library/heapq.rst | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst index d7658ae..6368cca 100644 --- a/Doc/library/heapq.rst +++ b/Doc/library/heapq.rst @@ -6,6 +6,7 @@ .. moduleauthor:: Kevin O'Connor .. sectionauthor:: Guido van Rossum <guido@python.org> .. sectionauthor:: François Pinard +.. sectionauthor:: Raymond Hettinger This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. @@ -138,6 +139,67 @@ values, it is more efficient to use the :func:`sorted` function. Also, when functions. +Priority Queue Implementation Notes +----------------------------------- + +A `priority queue <http://en.wikipedia.org/wiki/Priority_queue>`_ is common use +for a heap, and it presents several implementation challenges: + +* Sort stability: how do you get two tasks with equal priorities to be returned + in the order they were originally added? + +* Tuple comparison breaks for (priority, task) pairs if the priorities are equal + and the tasks do not have a default comparison order. + +* If the priority of a task changes, how do you move it to a new posistion in + the heap? + +* Or if a pending task needs to be deleted, how do you find it and remove it + from the queue? + +A solution to the first two challenges is to store entries as 3-element list +including the priority, an entry count, and the task. The entry count serves as +a tie-breaker so that two tasks with the same priority are returned in the order +they were added. And since no two entry counts are the same, the tuple +comparison will never attempt to directly compare two tasks. + +The remaining challenges revolve around finding a pending task and making +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) + 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 + + Theory ------ |