Python heapq替换优先级

Question

我试图使用Python的heapq实现Dijkstra的算法。如果发现指向单元格的路径较短，则该算法需要更改单元格的值。

我要用这张支票：

if curr_cell[0] + val < prev_cell[0]:  # value of new path is less than old value
    new_cell = (curr_cell[0] + val, prev_cell[1], curr_cell[1])
    heap[index] = new_cell
    heapify(heap)

然而，当在一个更大的迷宫上运行我的程序时，这需要很长时间，可能是因为heapify()调用。

更改堆条目的优先级的更有效方法是什么？

Answer 1

heapq库不支持有效地更新优先级，因为没有有效的方法来搜索堆。如果在O（n）时间内搜索堆并手动替换元素，则可以使用_siftup（）和_siftdown（）还原堆不变量。

或者，这里是我编写的一个兼容实现，它使用dict允许对堆索引进行O（1）查找。

https://github.com/elplatt/python-priorityq

Answer 2

一种可能的解决方案是将条目标记为已删除，并添加一个具有修订优先级的新条目。documentation提供了一个示例实现：

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 3

事实上，几年前我写了一个，你可能会觉得有用！

https://pypi.org/project/priorityq/