python - 从优先级队列中删除任意项

Question

如何从优先队列中删除任意项。假设我有一个用于作业的 PriorityQueue。我有一份工作想“取消”，所以我需要将其从队列中删除，我该怎么做？

更新

要添加到答案，一个相关的问题:https://stackoverflow.com/a/9288081/292291

Answer 1

我假设您正在使用 heapq。 documentation关于这个问题有这样的说法，这似乎很合理:

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.

文档提供了一些基本的示例代码来展示如何做到这一点，我在这里逐字复制:

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')