Python heapify實現運行時間

Question

我正在研究數據結構和算法，當時我應該實現在特定時間範圍內運行heapsort算法。下面是兩種實現：

def generateSwaps(): 
size=self._n 
    for root in range((size//2)-1,-1,-1): 
     root_val = self._data[root]    # save root value 
     child = 2*root+1 
     while(child<size): 
      if child<size-1 and self._data[child]>self._data[child+1]: 
       child+=1 
      if root_val<=self._data[child]:  # compare against saved root value 
       break 
      self._data[(child-1)//2]=self._data[child] # find child's parent's index correctly 
      self._swaps.append(((child-1)//2,child)) 
      child=2*child+1 
      # print(child) 
     self._data[(child-1)//2]=root_val  # here too, and assign saved root value 
    return self._data 

這裏，self._n是輸入的大小，self._data是需要形成爲heap.This實現元素的列表通行證具有低得多的運行測試時間（在給定的3秒時間限制內，最大迭代花費0.32秒）。

下面是第二個碼片，其悲慘失敗（與最大迭代以高達6秒）

for i in range(self._n//2 , -1, -1): 
     child_index = 0 
     if (2*i + 2) == self._n: 
     child_index = 2*i + 1 
     elif (2*i + 2) < self._n: 
     child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2])) 
     else: 
     child_index = 0 

     while self._data[i] > self._data[child_index]: 
     b = 0 
     print("child is smaller for n = " + str(i)) 
     print(child_index) 
     if child_index == 0: 
      break 
     else: 
      self._swaps.append((i, child_index)) 
      self._data[i], self._data[child_index] = self._data[child_index], self._data[i] 
      if child_index <= n//2: 
      i = child_index 
      else: 
      break 
      if (2*i + 2) == self._n: 
      child_index = 2*i + 1 
      elif(2*i + 2) < self._n: 
      child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2])) 
      else: 
      child_index = 0 

     print("hello work") 
     self._data[i], self._data[child_index] = self._data[child_index], self._data[i] 
     print(self._data) 

我想了解的是在運行時間如此大差異的原因。我認爲這可能是由於在while循環的每一步交換了列表項，但由於python中的列表基本上是一個數組，所以我意識到交換應該是恆定的時間步長（這是我的假設。錯了）。

預先感謝

Answer 1

所建議通過在上述評論user2357112和user2357112，問題是在下面的行中的.index（）操作。

child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2])) 

在陣列中找到一個元素的索引的Runitime爲O（n），因爲它需要步行通過陣列，直到在的價值。使過長運行時間在第二找到第一個匹配實現。在第一個實施中，這被替換爲直接比較考慮中的孩子和其鄰居孩子的價值，如下所示。

if child<size-1 and self._data[child]>self._data[child+1]: 
    child+=1 

由於數組有恆定時間訪問元素，因此上述實現是恆定時間，因此減少了運行時間。