How can I remove an arbitrary item from a priority queue. Suppose I have a PriorityQueue for jobs. I have a job I want to "cancel" so I need to remove it from the queue, how can I do that?
UPDATE
To add to the answer, a related question: https://stackoverflow.com/a/9288081/292291
I'm assuming you're using heapq. The documentation has this to say about this problem, which seems quite reasonable:
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 the existing entry as removed and add a new entry with the revised priority.
The documentation provides some basic example code to show 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')
Python's built-in PriorityQueue does not support removal of any item except the top. If you want any-item removal support, you'll need to implement your own queue (or find someone else's implementation).
