堆中的高效簿記

我試圖實現一個使用列表數據結構的堆。我還想跟蹤列表中元素的位置，以便輕鬆刪除。我的實現涉及遍歷整個列表以在插入/刪除組合後更新位置。恐怕這會增加從O（log n）到O（n）的時間複雜度。有沒有更好的方法來跟蹤元素的位置？目前，更新方法是照顧簿記。堆中的高效簿記

class heap(): 
    ''' Min-Heap''' 
    def __init__(self,G): 
     self.list=[0] #to ease dealing with indices, an arbitrary value at index 0 
     self.pos={} #holds position of elements with respect to list 
     self.G = G #Graph, contains the score for each element in G[element][2] 

    def update_pos(self): 
     self.pos = {} 
     for i in xrange(1,len(self.list)): 
      self.pos[self.list[i]]=i 

    def percUp(self): #percolate up, called by insert method 
     start = len(self.list)-1 
     while start//2>0: 
      if self.G[self.list[start/2]][2] > self.G[self.list[start]][2]: 
       self.list[start/2],self.list[start] = self.list[start],self.list[start/2] 
      start = start//2 

    def insert(self,element): 
     self.list.append(element) 
     self.percUp() 
     self.update_pos() 

    def percDown(self,start=1): #percolate down, called by extract_min method 
     while 2*start < len(self.list): 
      min_ind = self.getMinInd(start) 
      if self.G[self.list[start]][2] > self.G[self.list[min_ind]][2]: 
       self.list[start],self.list[min_ind] = self.list[min_ind],self.list[start] 
      start = min_ind 

    def extract_min(self): 
     self.list[-1],self.list[1] = self.list[1],self.list[-1] 
     small = self.list[-1] 
     self.list = self.list[:-1] 
     self.percDown() 
     self.update_pos() 
     return small 

    def delete(self,pos): 
     self.list[-1],self.list[pos] = self.list[pos],self.list[-1] 
     self.pos.pop(self.list[pos]) 
     self.list = self.list[:-1] 
     self.percDown(pos) 
     self.update_pos() 

    def getMinInd(self,start): 
     if 2*start+1 > len(self.list)-1: 
      return 2*start 
     else: 
      if self.G[self.list[2*start]][2]<self.G[self.list[2*start+1]][2]: 
       return 2*start 
      else: 
       return 2*start+1

來源

2016-08-24 dpk

我認爲你的問題更適合[Code Review Stack Exchange]（http://codereview.stackexchange.com）網站。 –

如果你正在構建一個二進制堆，我知道加快任意刪除或改變優先級的最好方法是創建一個哈希映射。關鍵是優先級隊列中的項目，並且該值是其在數組中的當前位置。將項目插入隊列時，可以使用項目的當前位置向哈希映射添加條目。

然後，每次項目在隊列中移動，您更新其散列映射中的值。因此，每次在插入或移除期間進行交換時，都會更新該哈希映射中交換項目的值。

要刪除的任意的項目，那麼，你千萬以下：

查找該項目的哈希映射位置。
刪除哈希映射中的項目條目。
將堆中的最後一項移動到移除的項的位置，並更新其在散列圖中的位置。
根據需要在堆中向上或向下篩選新項目，更新散列映射中所有受影響的節點的位置。

這個工作相當不錯，雖然如果你的堆很大，它在內存方面會非常昂貴。

其他堆數據結構（如斐波那契堆，配對堆，偏斜堆或甚至是實現爲二叉樹的二進制堆）與單個堆節點而非數組中的隱式節點一起工作，因此可以直接訪問，而無需需要一箇中間散列表。它們確實需要比作爲數組實現的二進制堆更多的內存，但可能效率更高。順便說一下，如果您決定嘗試其中一種替代結構，我建議您查看Pairing堆。它的漸近性能幾乎和斐波那契堆一樣好，而且它的更容易實現。我的實際表現還沒有很好的數字。

來源

2016-08-24 17:10:11

堆中的高效簿記

回答

相關問題