从优先队列中移除任意项

Question

我该如何从优先队列中移除一个特定的项目呢？假设我有一个用于处理工作的优先队列。我有一个工作想要“取消”，所以我需要把它从队列中移除，我该怎么做呢？

更新

为了补充这个问题，还有一个相关的问题： https://stackoverflow.com/a/9288081/292291

Answer 1

Python自带的PriorityQueue（优先队列）只能移除最上面的那个项目，其他的项目是不能直接删除的。如果你想要能够删除队列中任意一个项目，那你就需要自己写一个队列，或者找别人写好的代码来用。

Answer 2

我猜你是在使用 heapq 这个库。它的文档对这个问题有一些很合理的解释：

剩下的挑战主要是找到一个待处理的任务，以及修改它的优先级或完全删除它。找到一个任务可以通过一个字典来实现，这个字典指向队列中的某个条目。

删除这个条目或改变它的优先级就比较困难了，因为这样会破坏堆的结构特性。所以，一个可能的解决办法是将现有的条目标记为已删除，然后添加一个新的条目，带有更新后的优先级。

文档中提供了一些基本的示例代码，展示了如何实现这一点，我在这里逐字复制：

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