Python：heapify k階最小堆？

-1

我正在爲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]。看起來我移動到頂端的元素永遠不會冒泡。

來源

2017-04-20 Nicole R

你的問題是什麼？或錯誤？ –

當我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

來源

2017-04-21 02:58:35

Python：heapify k階最小堆？

回答

相關問題