置き換えの選択ソート

Question

私はこのアルゴリズムを実装しようとしてきましたが、どこから始めたらいいかわかりません。基本的に、私は、トップレベルが最小（minHeap）であること、またはトップレベルがすべての最大値（maxHeap）であることを2つの方法で実装することができると理解しています。私は2つの方法のいずれかについてたくさんのことを知っていて、実際にそれを実装する方法については把握できませんでした。私は一般的にアイデアを得ることはできません、私は言うでしょう、誰もこの作品の仕方を教えてくださいできますか？ minHeapの動作方法やmaxHeapのように。 ありがとうございます！

Answer 1

私は、配列内のバイナリヒープ実装の基本的な知識があると仮定しています。

昇順にソートする整数の配列があるとします。 1つの方法は、配列内の項目を並べ替えて、最大ヒープを形成することです。

次に、ヒープ内の最後の項目と最上位項目（配列内の最大項目）を入れ替え、ヒープ数を1減らし、上から下にある項目をヒープ内の新しい場所に移動します。最後に、配列の最初の項目が次に大きい項目になります。あなたはすべてのアイテムと配列の並べ替えを繰り返す。

小さな例を考えてみましょう。アレイ[4,7,6,1,3,5,2]が与えられた場合、Floydのアルゴリズムを使用してヒープに並べ替えます。

for (int i = array.length/2; i >= 0; i--) 
{ 
    siftDown(i); 
} 

これはO（n）操作です。

完了したら、配列はバイナリヒープに配置されます。この場合、ヒープが[7,4,6,1,3,5,2]、または次のようになります。[2,4,6,1,3,5,7]を：だから

 7 
    4 6 
    1 3 5 2 

、私たちは私たちを与えて、最後の項目でルートアイテムを入れ替えます。私たちは、カウントを減少させ、その適切な場所まで2をふるいにかける、与える：[6,4,5,1,3,2,7]を、またはヒープ表現：

 6 
    4 5 
    1 3 2 

（我々は数を減少させたので、私は7を省略しかし、それは、配列の末尾にはまだです。再び）

、ヒープ内の最後の項目でトップのアイテムを入れ替える：[2,4,5,1,3,6,7]、回数を減らし、ダウン取捨選択：[5,4,2,1,3,6,7]：

 5 
    4 2 
    1 3 

あなたは、ヒープ内の残りの5つの項目のことを継続した場合、あなたは終わるでしょうソートされた配列を持ちます。

このためのコードは非常に簡単です：

int count = array.length-1; 
while (count > 0) 
{ 
    swap(array[0], array[count]); 
    --count; 
    siftDown(0); 
} 

あなたは降順のソートを行いたい場合は、最大ヒープで上記の操作を行い、その後、アレイ（O（1）を逆にすることができますいずれか操作）、または開始するためのミニヒープを構築できます。

siftDown方法は、単にバイナリヒープ建設のための規則に従って、その適切な場所まで項目を移動します。

void siftDown(int index) 
{ 
    // Left child is at index*2+1. Right child is at index*2+2; 
    while (true) 
    { 
     // first find the largest child 
     int largestChild = index*2+1; 
     // if left child is larger than count, then done 
     if (largestChild >= count) 
     { 
      break; 
     } 
     // compare with right child 
     if (largestChild+1 < count && array[largestChild] < array[largestChild+1]) 
     { 
      ++largestChild; 
     } 

     // If item is smaller than the largest child, then swap and continue. 
     if (array[index] < array[largestChild]) 
     { 
      swap(array[index], array[largestChild]); 
      index = largestChild; 
     } 
     else 
     { 
      break; 
     } 
}