最大堆投擲指數越界

Question

下面是我的最大堆實現。我可以真正弄清楚爲什麼我得到索引超出界限的錯誤。我已經指定數組self.heap

class heap: 
    def __init__(self): 
     self.heapsize=0 
     self.heap=[0] 
    def builheap(self,list): 
     self.heapsize = len(list) 
     self.heap=list 
     for i in range(len(list)//2, 0, -1): 
      self.maxheap(self.heap,i) 
    def maxheap(self, list, index): 
     if list[2*index]<=self.heapsize and list[2*index]>list[index]: 
      largest=list[2*index] 
     else: 
      largest=index 
     if list[2*index+1]<= self.heapsize and list[2*index+1]>list[index]: 
      largest=list[2*index+1] 
     if largest!=index: 
      tmp = list[index] 
      list[index] = list[largest] 
      list[largest] = tmp 
      maxheap(list,largest) 

h=heap() 
h.builheap([16,14,10,8,7,9,3,2,4,1]) 

錯誤：

Traceback (most recent call last): 
    File "heap.py", line 24, in <module> 
    h.builheap([16,14,10,8,7,9,3,2,4,1]) 
    File "heap.py", line 9, in builheap 
    self.maxheap(self.heap,i) 
    File "heap.py", line 11, in maxheap 
    if list[2*index]<=self.heapsize and list[2*index]>list[index]: 
IndexError: list index out of range 

Answer 1

你有這樣的代碼：

if list[2*index]<=self.heapsize and list[2*index]>list[index]: 
     largest=list[2*index] 
    else: 
     largest=index 
    if list[2*index+1]<= self.heapsize and list[2*index+1]>list[index]: 

你試圖索引列表檢查，看看前該指數超出了名單的界限。此外，您想檢查索引以查看它是否在界限內，而不是檢查該索引處的內容是否在界限內。

它應該是：

if 2*index<=self.heapsize and list[2*index]>list[index]: 
     largest=list[2*index] 
    else: 
     largest=index 
    if 2*index+1<= self.heapsize and list[2*index+1]>list[index]: 

這我不清楚你的根是否爲0或1。

如果根節點是list[0]，那麼你的計算應該是(2*index) + 1和(2*index)+2。您假定根目錄爲list[1]的計算結果。