堆中的高效簿记

Question

我正在尝试使用列表数据结构实现堆。我还想跟踪列表中元素的位置，以便于删除。我的实现涉及遍历整个列表以更新 insert/delete 组合后的位置。恐怕这会将时间复杂度从 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

Answer 1

如果您要构建二进制堆，我知道加快任意删除或更改优先级的最佳方法是创建哈希映射。键是优先队列中的项目，值是它在数组中的当前位置。当您将一个项目插入队列时，您将一个条目添加到具有该项目当前位置的哈希映射中。

然后，每次一个项目在队列中移动时，您都会在散列映射中更新它的值。因此，每次在插入或删除期间进行交换时，都会更新该哈希映射中交换项目的值。

要删除任意项，请执行以下操作：

在哈希图中查找项目的位置。
删除项目在哈希映射中的条目。
将堆中的最后一项移动到已移除项的位置，并更新其在哈希映射中的位置。
根据需要在堆中向上或向下筛选新项目，更新哈希映射中所有受影响节点的位置。

这工作得相当好，但如果您的堆很大，它在内存方面可能会非常昂贵。

其他堆数据结构，例如 Fibonacci 堆、配对堆、Skew 堆，甚至作为二叉树实现的二叉堆使用单个堆节点而不是数组中的隐式节点，因此可以直接访问而无需需要一个中间散列 table。它们确实需要比作为数组实现的二进制堆更多的内存，但可能更有效。

顺便说一句，如果您决定尝试其中一种替代结构，我建议您看一下配对堆。它的渐近性能几乎与 Fibonacci 堆一样好，而且更容易实现。我还没有关于它在现实世界中的表现的任何好数字。

堆中的高效簿记

Efficient bookkeeping in heap

python

heap