Pythonのヒープソート時間計算

Question

私は正常に動作しているヒープソート、次のコードを書いている：

class Heap(object): 
     def __init__(self, a): 
      self.a = a 

     def heapify(self, pos): 
      left = 2*pos + 1 
      right = 2*pos + 2 
      maximum = pos 

      if left < len(self.a) and self.a[left] > self.a[maximum]: 
       maximum = left 
      if right < len(self.a) and self.a[right] > self.a[maximum]: 
       maximum = right 

      if maximum != pos: 
       self.a[pos], self.a[maximum] = self.a[maximum], self.a[pos] 
       self.heapify(maximum) 

     def buildHeap(self): 
      for i in range(len(self.a)/2, -1, -1): 
       self.heapify(i) 

     def heapSort(self): 
      elements = len(self.a) 
      for i in range(elements): 
       print self.a[0] 
       self.a[0] = self.a[-1] 
       self.a = self.a[:-1] 
       self.heapify(0) 

     def printHeap(self): 
      print self.a 

if __name__ == '__main__': 
    h = Heap(range(10)) 
    h.buildHeap() 
    h.printHeap() 
    h.heapSort() 

しかし、ここでの機能heapSortが原因リストのスライスに、時間O(n^2)がかかりますようです。 （サイズ 'n'のリストについては、それを 'n-1'にスライスするとO（n-1）時間かかる）。 私の考えが正しいかどうか誰にでも確認できますか？ の場合、heapSortの最小限の変更は、O(nlogn)で動作させるにはどうすればよいですか？

Answer 1

はい、あなたは正しいと思います。それはより速く行うために、このようなものに置き換えますと

self.a = self.a[:-1] 

を：リストの

self.a.pop() 

pop()メンバ関数は削除され、一定の時間複雑で、リストの最後の要素を返します。

listは、連続したメモリとして格納されます。つまり、listのすべての要素が順番に格納されます。このため、listの中に要素を挿入するのは非常に高価です：Pythonは、挿入する場所の後にあるすべての要素を1つ下にシフトして、新しい要素のための領域を確保する必要があります。しかし、listの最後の要素を単純に削除するには、Pythonがその要素を消去するだけで済むため、時間がかかりません。