(少なくとも理論上は) ヒープをソートする最速の方法は何ですか?

StackOverflow https://stackoverflow.com/questions/113991

  •  02-07-2019
  •  | 
  •  

質問

ヒープとは、以下が適用されるリストです。

l[i] <= l[2*i] && l[i] <= [2*i+1]

のために 0 <= i < len(list)

インプレース並べ替えを探しています。

役に立ちましたか？

解決

データをヒープに入れることで、すでにヒープ ソートの半分が完了しています。必要なのは、ヒープ ソート アルゴリズムの 2 番目の部分を実装することだけです。これは、ヒープ配列でクイックソートを使用するよりも高速になるはずです。

勇気があるなら、実装してみるのもいいかもしれません スムーズソート, 、ほぼソートされたデータの場合、ヒープソートよりも高速です。

他のヒント

ヒープソートを使用するだけです。それはその場にあります。それが最も自然な選択でしょう。

ヒープをそのまま使用し、他のアルゴリズムでソートすることもできます。その後、ソートされたリストからヒープを再構築します。クイックソートは、ヒープがすでに事前にソートされているため、最悪の場合の O(n²) 順序で実行されないことが確実であるため、適切な候補です。

比較関数が高価な場合は、この方が高速になる可能性があります。ヒープソートは比較関数を頻繁に評価する傾向があります。

ヒープをその場でソートするのは、ある種の仕事のように聞こえます ヒープソート.

おそらく埋め込みアプリのせいでメモリに制約があるのではないかと思います。

すでにヒープがあるので、第 2 フェーズを使用することはできませんか? ヒープソート?それは適切な場所で機能し、素晴らしく効率的になるはずです。

インプレース並べ替えの場合、最も速い方法が次のとおりです。コード内の off-by-one エラーに注意してください。このメソッドでは、反転されたソートされたリストが得られますが、これは最終ステップで元に戻す必要があることに注意してください。max-heap を使用すると、この問題は解決します。

一般的なアイデアは次のとおりです。最小の要素 (インデックス 0) をヒープ内の最後の要素と交換し、ヒープのプロパティが復元されるまでその要素をバブルダウンし、ヒープのサイズを 1 つ縮小して繰り返します。

David Mackay が実証しているように、これは非インプレース並べ替えの絶対に最速の方法ではありません。 ここ - 最も小さい可能性が高い要素を、ヒープの一番下の行に置くのではなく、一番上に置くと、より良い結果が得られます。

時間計算量は最悪の場合 T(n.log n) です。おそらく log n (ヒープの高さ) を伴う n 回の反復が while ループを通過します。

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

ヒープの上部にある項目を 1 つずつ読み取ります。基本的に、これで得られるのはヒープソートです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top