堆中的高效簿记

我试图实现一个使用列表数据结构的堆。我还想跟踪列表中元素的位置，以便轻松删除。我的实现涉及遍历整个列表以在插入/删除组合后更新位置。恐怕这会增加从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

堆中的高效簿记

回答

相关问题