這是我的場景。我想實現A *（使用Python），而不必求助於線性時間min或操作。我需要一堆能夠有效地獲得最低重量的物品。支持修改元素的堆？
我的直接回復是'Easy！我會用heapq！'然後我發現生活並不像我們希望的那樣簡單。事實證明，這種策略對於A *的關鍵點之一來說並不理想。當考慮到孩子時，我需要偶爾更新已經在堆上的孩子的分數。
對於那些記憶A *已經失效的人來說，它的要點是我想要一個元素，修改它的權重，並修改堆來反映變化，所有這些都在次線性時間。
有什麼建議嗎？
出於複雜性的考慮，你會想嘗試一個二項式或Fibonacci堆;似乎在Python中有兩個實現，但不是生產級庫。儘管如此，二進制或d-ary堆可能在實踐中工作得更快。 heapq頁面提到了如何進行更新（保留對插入到堆中的項目的引用，將其標記爲無效，然後插入新版本）。儘管如此，在更新後維護堆屬性的算法更快。查看http://en.wikipedia.org/wiki/D-ary_heap以瞭解用於快速更新的算法，但您可能需要在這些數組的頂部實現自己的堆。
確實，heapq和Queue.PriorityQueue中的堆函數都沒有任何功能。它可能需要大致相同的時間來A：在你的博客上寫一個咆哮或B：你自己實現一個。
我總是最終實現自己的Heap類型版本，確切的原因是您實際上無法在Heap中進行搜索，而所有有效的方法都需要「指向元素的指針」作爲輸入。
通常，我將Heap實現爲Items的非結構化容器和指向項的指針（或indeces）的堆的組合。如果在項目中保留一個指向Heap位置的指針，則有一個直接的雙向鏈接： a）給定Heap元素（例如，由extractMin返回，或者在比較過程中）：取消引用指針，並且獲得你的物品。 b）給定一個項目（例如通過Graph算法的鄰接列表）：將指針傳遞給你想要的任何更新函數。當然，這會導致空間開銷（每個Item有2個額外的指針/整數），但它使堆重構非常便宜（交換幾個指針而不是交換整個項），這反過來使添加一些額外的衛星數據到您的項目。