Python heapify実装の実行時間

Question

私は、特定の時間枠で実行するヒープソートアルゴリズムを実装するはずだったデータ構造とアルゴリズムのコースを取っています。以下の2つの実装である：ここ

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秒件まで取って最大の反復で）無残に失敗した2番目のコード部分

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

で

おかげで問題が下の行に.INDEX（）操作であった、上記のコメントにuser2357112とuser2357112によって示唆されるように。それはあなたがvalue.This第二に過度に長い実行時間が原因で最初の一致が見つかるまで配列を歩く必要とする配列エレメントのインデックスを見つける

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 

アレイは要素に対して一定の時間アクセスを持つので、上記の実装は一定の時間であり、したがって実行時間が短縮されます。