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

Question

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

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

為に0 <= i < len(list)

その場での並べ替えを探しています。

Answer 1

ヒープソートを使用するだけです。インプレースです。それが最も自然な選択でしょう。

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

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

Answer 2

データをヒープに入れることで、すでにヒープソートの途中です。ヒープ ソート アルゴリズムの 2 番目の部分を実装するだけです。これは、ヒープ配列でクイックソートを使用するよりも高速です。

勇気があれば、ほぼソートされたデータのヒープソートよりも高速なSmoothsortの実装に挑戦できます。

Answer 3

ヒープをその場で並べ替えるのは、 Heap Sortの仕事のように聞こえます。

おそらく組み込みアプリのメモリに制約があると思いますか？

Answer 4

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

Answer 5

インプレース ソートの場合、最速の方法は次のとおりです。コード内のオフバイワン エラーに注意してください。このメソッドは、最終ステップで元に戻す必要がある逆順のソート済みリストを提供することに注意してください。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--:
  }

Answer 6

ヒープの一番上から項目を 1 つずつ読み取ります。基本的に、あなたが持っているのはヒープソートです。