ヒープソープのヒープ構造の最適化

Question

ヒープを使用してヒープソートを実装しています。これを行うために、ソートされる各値が挿入されます。挿入メソッドはheapifyUp()（別名siftUp）を呼び出すので、別の値が挿入されるたびにheapifyUpが呼び出されます。これが最も効果的な方法ですか？

また、すべての要素を挿入し、heapifyUpを呼び出すこともできます。私はheapifyUpをそれぞれ呼び出さなければならないと思いますか？このようにしていますか？

Answer 1

各要素を挿入すると、O（n log n）時間でヒープが構築されます。すべての要素を配列に追加してから、heapifyUp()を繰り返し呼び出すのと同じことです。

Floyd's Algorithmは、O（n）時間内にヒープボトムアップを構築します。アイデアは、あなたが順序どおりの配列を取り、真ん中から始めて、の各項目を適切な場所に移動させます。アルゴリズムは次のとおりです。

for i = array.length/2 downto 0 
{ 
    siftDown(i) 
} 

最後の長さ/ 2の配列内のアイテムが葉であるため、途中で開始します。彼らはふるい落とすことはできません。中から上に向かって作業することで、移動する必要のあるアイテムの数を減らすことができます。

差

以下の例の実施例では、ヒープの中に7つの項目の配列を回し、仕事の量の違いを示しています。

heapifyUp（）メソッド

[7,5,6,1,2,3,4] (starting state) 

端から始まり、バブルアイテムアップ。

適切な場所に移動し4

[7,5,4,1,2,3,6] 
[4,5,7,1,2,3,6] 

その場所に移動し3

[4,5,3,1,2,7,6] 
[3,5,4,1,2,7,6] 

ムーブ2ムーブ1

[3,2,4,1,5,7,6] 
[2,3,4,1,5,7,6] 

その場所にその場所に

[2,1,4,3,5,7,6] 
[1,2,4,3,5,7,6] 

ヒープが整理されました。これは、8つのスワップを取って、あなたはまだ確認してください4、2、および1

中間点でのフロイドのアルゴリズム

[7,5,6,1,2,3,4] (starting state) 

スタートとダウン取捨選択する必要があります。 0から始まる7つのアイテムの配列では、中間点は3です。

その場所に移動し1

[7,5,6,1,2,3,4] (no change. Remember, we're sifting down) 

その場所に移動し6

[7,5,3,1,2,6,4] 

その場所に移動5

[7,1,3,5,2,6,4] 
[7,1,3,4,2,6,5] 

その場所に移動7

[1,7,3,5,2,6,4] 
[1,2,3,5,7,6,4] 

これで完了です。それは5回のスワップを必要とし、チェックする他に何もありません。