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

Question

如何从优先级队列中删除任意项.假设我有一个PriorityQueue作业.我有一份工作要"取消",所以我需要将它从队列中删除,我该怎么做？

UPDATE

要添加答案,请提供相关问题:https://stackoverflow.com/a/9288081/292291

Answer 1

我假设你正在使用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')

Answer 2

Python 的内置PriorityQueue不支持删除除顶部之外的任何项目。如果您想要任何项目删除支持，您需要实现自己的队列（或找到其他人的实现）。