這個堆的實現有什麼問題？

-4

我的插入方法不正確，我不知道爲什麼。我最小的方法錯誤，而不是「內建函數或對象不可下標」這個堆的實現有什麼問題？

我認爲我對堆的概念理解是好的。但其壓裂令人沮喪，當實際insert把它寫下來:(

class Heap: 
    def __init__(self): 
     self.array = [] 

    def find_children(self, index): 
     """ return both the left and right children """ 
     return index * 2 + 1, index * 2 + 2 

    def insert(self, value): 
     """ append node value to the array, then bubble up 
     to its rightful place 
     """ 
     self.array.append(value) 
     index = self.array.index(value) 

     while index > 0 or self.array[index] < self.array[index // 2 - 1]: 
      if self.array[index] < self.array[index // 2 - 1]: 
       temp = self.array[index] 
       self.array[index] = self.array[index // 2 - 1] 
       self.array[index // 2 - 1] = temp 
      index = index // 2 - 1 

    def min(self): 
     """ remove the min at the root, then bubble down to 
     maintain heap property 
     """ 
     minimum = self.array[0] 
     self.array[0] = self.array[-1] 
     self.array.pop() 

     index = self.array.index[minimum] 

     while index <= len(self.array): 
      leftChildIndex, rightChildIndex = self.find_children(index) 
      minChild = min(self.array[leftChildIndex], self.array[rightChildIndex]) 
      if self.array[index] > minChild: 
       temp = self.array[index] 
       self.array[index] = minChild 
       minChild = temp 
      index = minChild 

     return minimum 

    def p(self): 
     return self.array

來源

2016-07-08 MAA

你在'self.array.index [最小]處使用了錯誤的括號' – jonrsharpe

@jonrsharpe明白了..這需要一個投票權呵呵 – MAA

只是爲了澄清倒票：錯誤應該有精確的說明問題在哪一行。忽略這些信息，只是傾銷你的代碼讓其他人進行工作並不完全禮貌。 – MisterMiyagi

線self.array.index(value)是危險的。會發生什麼，如果你這樣做已經存在於堆值的插入？你應該使用len(self.array)代替（你「再附加到陣列，因此這將是最後一個元素）。

同樣，在min，您可以有效地這樣做。你不需要來搜索索引，你已經知道了。

你可能實際上想要維護你自己的「leng th「和」容量「屬性，因爲增長和縮小後備陣列將壓倒你期望的日誌（n）。

來源

2016-07-08 08:41:08 Vatine

這個堆的實現有什麼問題？

回答

相關問題