ヒープソートについてPythonコードを改善するにはどうすればよいですか？

Question

私は、Leetcode 217. Contains Duplicateのヒープソートプログラムを、Pythonの組み込みソートメソッドを使うのではなく、以下のように書くことを試みました。 Leetcodeはヒープソート方法を受け入れるべきですが、私のヒープソートプログラムはうまく動作しますが、何らかの理由でLeetcodeから実行時の拒否が得られます。誰も助けることができますか？解決

、コードの下にヒープを初期化するために、フロイドのアルゴリズムを使用して再編集され、Leetcode

def heapsort(nums): 

    def swap(i, j): 

     nums[i], nums[j] = nums[j], nums[i] 


    def sift(start, size): 

     l = (start << 1) + 1 # Do not forget() for << 
     r = l + 1 
     largest = start 
     if l <= size - 1 and nums[start] < nums[l]: 
      largest = l 
     if r <= size - 1 and nums[largest] < nums[r]: 
      largest = r 
     if largest != start: 
      swap(start, largest) 
      sift(largest, size) 


    size = len(nums) 

    # Initialize heap (Floyd Algorithm) 
    end = (size >> 1) - 1 
    while end >= 0: 
     sift(end, size) 
     end -= 1 
    swap(0, size - 1) 
    size -= 1 

    # Heapify recursively 
    while size > 1: 
     sift(0, size) 
     swap(0, size - 1) 
     size -= 1 

Answer 1

コードが多すぎます。削除するすべてのアイテムでヒープ全体を再構築しています。だから、O（n log n）アルゴリズムはO（n^2）の代わりになるはずです。

基本的に、あなたのコードは、これをやっている：ヒープを再配置

while array is not empty 
    rearrange array into a heap 
    extract the smallest item 

は、最高の状態で、O（n）の時間がかかります。最小のものを抽出するにはO（log n）が必要です。あなたのアルゴリズムはO（n^2 + n log n）です。

実際、下から上にヒープを構築する方法は、それ自体O（n log n）です。ヒープソートアルゴリズムは実際にはO（（n + 1）*（n log n））です。いずれにしても、これは非常に最適ではないアルゴリズムです。

ヒープソートの背景にあるヒントは、のヒープに配列を配置することです。これはO（n）操作です。アルゴリズムはかなり簡単です：

for i = heap.length/2 downto 1 
    siftDown(i) 

これは、発明者の後にFloyd's algorithmと呼ばれています。

配列の中央で開始し、をに絞り込みます。アイデアは、最後のn/2個のアイテムが葉ノードであるため、とにかくそれらを落とすことができないということです。 n/2で始まり、逆方向に作業することで、O（n）時間内にアレイ全体をヒープ化できます。アレイはヒープに配置された後

、我々は次の操作を行います。ヒープに

while heap is not empty 
    output the item at heap[0] 
    move the item at the end of the heap to heap[0] 
    reduce the count of items by 1 
    siftDown(0) 

項目[0]ヒープ内に残っている最小の項目であるので、我々は出力。その後、ヒープ全体を再構築する必要はありません。ヒープ内の最後のアイテムを取り出し、一番上に置き、それを所定の位置に移動するだけです。残りのヒープは有効なままです。

これらの変更を行うと、実行時間が短縮されるはずですが、コードが受け入れられるかどうかはわかりません。重複を確認する別の方法があります。余分なスペースはO（n）必要ですが、ソートよりも高速です。

アイデアは、ハッシュテーブルを作成し、そのアイテムがハッシュテーブルに含まれているかどうかを確認しながら配列を調べることです。そうでない場合は、追加します。既にテーブルに入っている場合は、重複しています。Harold氏は、Pythonにはsetというタイプがあり、このようなことを簡単に行うことができます。

Answer 2

に、ヒープ・ソートといえばを通過した、heapq Pythonモジュールを検討します。この目的のために存在します - ヒープキューアルゴリズムの実装を提供します。それはあまり便利ではありませんが、手軽に設計されていますwrappers - あなたは自分でそれをGoogleにすることができます。

重複を見つけると、n log(n)ソートアルゴリズムは十分に効率的であってはなりません。 Python set組み込みを見てみましょう！