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