Removing an arbitrary item from the priority queue

Question

How to remove an arbitrary element from the priority queue. Suppose I have a PriorityQueue for jobs. I have a job that I want to “cancel”, so I need to remove it from the queue, how can I do this?

UPDATE

To add to the answer, a question related to this: https://stackoverflow.com/a/212618/

Answer 1

I assume you are using heapq . The documentation has this about it, which seems quite reasonable:

The remaining problems are related to finding a pending task and making changes to the priority or complete deletion. A task search can be done with a dictionary pointing to an entry in the queue.

Deleting a record or changing its priority is more difficult because it destroys the invariants of the heap structure. So, a possible solution is to mark the existing record as deleted and add a new record using the revised priority.

The documentation contains some basic code example showing how this can be done, which I reproduce here verbatim:

 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] entry_finder[task] = entry heappush(pq, entry) 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 task is not REMOVED: del entry_finder[task] return task raise KeyError('pop from an empty priority queue') 

Answer 2

The built-in PriorityQueue Python does not support the removal of any item except the top one. If you need support for deleting items, you need to implement your own queue (or find another implementation).