從堆中刪除元素

Question

我試圖實施AStar搜索算法，並且無法從邊緣（打開列表）中刪除元素。我把我的Cells在這樣的：

heapq.heappush(myHeap, (priority, cell) 

我的手機類看起來是這樣的：

class Cell(object): 
    def __init__(self, x, y): 
     self.X = int(x) 
     self.Y = int(y) 
     self.G = float("inf") 
     self.parent = None 

    def __lt__(self, other): 
     return (self.X, self.Y) < (other.X, other.Y) 

    def __eq__(self, other): 
     return int(self.X) == int(other.X) and int(self.Y) == int(other.Y) 

有沒有一種方法，我可以做heapq.remove(cell)或heapq.heappop(cell)刪除從堆的條目，然後reheapify它？

目前，我正在做這樣的，但我不認爲這是正常工作，因爲我得到一個無限循環有時是：

def remove(self, item): 
    index = 0 

    for i in range(len(myHeap)): 
     if(myHeap[i][1] == item): 
      index = i 

    # Move slot to be removed to top of heap 
    while index > 0: 
     up = int((index + 1)/2 - 1) 
     self.heap[index] = self.heap[up] 
     index = up 

    # Remove top of heap and restore heap property 
    heapq.heappop(myHeap) 

任何幫助，將不勝感激。

Answer 1

您也可以在列表myHeap上使用常規列表方法。因此，首先從列表中刪除某些特定的元素，然後heapify並與新的優先推動的元素：

myHeap.remove((priority, cell)) 
heapq.heapify(myHeap) 
heapq.heappush(myHeap, (new_priority, cell))