python heapq替换优先级

我正在尝试使用Python的heapq来实现Dijkstra的算法。该算法需要改变一个单元格的值，如果发现一条较短的路径导致它。python heapq替换优先级

我做了这个检查：

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()通话。

更改堆入口优先级的更有效方法是什么？

来源

2017-10-08 MarksCode

一个可能的解决方案是将条目标记为已删除并添加一个新的条目与修改后的优先级。所述documentation提供了一个示例实现：通过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'

来源

2017-10-08 22:37:44

您能否帮我理解itertools.count（）的用法。我不太明白。 – MarksCode

'itertools.count（）'只是产生连续的数字。将计数添加到像[[priority，count，task]]这样的条目可以确保具有相同优先级的条目按照它们的添加顺序进行处理。我想，你可以跳过Dijkstra算法。 –

嗨尤金，我已经在官方文档中检查过了，但我有一个问题。这个实现不是以堆的大小来衡量吗？如果您经常更新优先级，是不是会使堆大小变大？有没有更有效的方式来使用heapq中的私有方法？ – SilverSlash