Python：heapify k阶最小堆？

问题描述：

我正在为K-Order Min-heap创建一个类。我将堆作为列表存储。我在执行remove_min时遇到了问题。我知道删除最小堆的过程是：Python：heapify k阶最小堆？

删除第一个元素。这是最低限度。
交换第一个元素和最后一个元素。
向下冒泡新的顶部元素，直到它满足堆属性。

所以我需要一个remove_min和一个辅助功能，bubbledown。我不能使用heapq，因为它只占二进制堆，这个类需要一个k阶堆。这是我到目前为止：

class KHeap: 
    def __init__(self, lst=[], k=2): 
     self.heap = [] 
     self.k = k #order of heap 
     for v in lst: 
      self.insert(v) 

    def children(self, i): #returns a list of the children of the item in index i 
     heap = self.heap 
     result = [] 
     for x in range(self.k*i+1, self.k*i+self.k+1): 
      if x<len(heap): 
       result.append(heap[x]) 
      else: 
       pass 
     return result 

    def parent(self, i): #returns the parent of item in index i 
     heap = self.heap 
     if i==0: 
      return None 
     result = i//self.k 
     return heap[result] 

    def bubbleup(self, i): 
     if i == 0: 
      return None 
     elif self.heap[i] < self.parent(i): 
      self.heap[i], self.heap[i // self.k] = self.heap[i // self.k], self.heap[i] 
      self.bubbleup(i // self.k) 

    def insert(self, value): #use bubbleup 
     self.heap.append(value) 
     self.bubbleup(len(self.heap)-1) 

    def bubbledown(self, i, d=1): 
     if i==0: 
      return None 
     small = i 
     for k in range(self.children(i)): 
      if self.heap[k]<self.heap[small]: 
       small = k 
     self.heap[i], self.heap[small] = self.heap[small], self.heap[i] 
     self.bubbledown(small) 

    def remove_min(self): #use bubbledown 
     if len(self.heap) == 0: 
      return None 
     if len(self.heap) == 1: 
      return self.heap.pop() 
     minimum = self.heap[0] 
     self.heap[0] = self.heap.pop() 
     self.bubbledown(0) 
     return minimum

现在，当我remove_min，结果不heppified。例如，如果我有一个三元堆[1, 10, 18, 22, 15, 30], k=3并删除最小值，则结果为[30, 10, 18, 22, 15]。看起来我移动到顶端的元素永远不会冒泡。

你的问题是什么？或错误？ –

当我remove_min时，结果没有被heapified。例如，如果我有一个三元堆'[1,10,18,22,15,30]，k = 3'，并删除最小值，结果是[30,10,18,22,15] 。看起来我移动到顶端的元素永远不会冒泡。（我将把它放在原文中） –

第一个问题是，在你的remove_min中，你调用self.bubbledown（0）。并在你的bubbledown，第一行是如果我== 0：返回无。因此，每次您调用bubbledown（0）时，没有任何变化。修复并重试。 –

答

所以我发布了一个迭代版本，它可以解决i == 0问题。

def bubbledown(self, i, d=1): 
    small = i 
    size = len(self.heap) 
    while (i < size): 
     // find the smallest child 
     for k in range(self.children(i)): 
      if self.heap[k] < self.heap[small]: 
       small = k 
     self.heap[i], self.heap[small] = self.heap[small], self.heap[i] 
     // stop here 
     if small == i: 
      break 
     else: 
      i = small

Python：heapify k阶最小堆？

相关推荐