[解決済み] 配列をヒープ化するためのヒープにおけるsiftUp, siftDown操作

質問

親要素の値が子要素の値より大きい場合、MAX-HEAPIFY操作を想定する。

• siftDown は、小さすぎるノードをその最大の子ノードと交換し（それによって下に移動し）、少なくとも両方のノードと同じ大きさになるまで交換します。 その下にある。

• siftUp は、大きすぎるノードをその親と交換します（それによって、ノードを移動させます）。 を上にして、上のノードより大きくならないようにします。buildHeap 関数は、ソートされていないアイテムの配列を受け取り はすべてヒープ特性を満たす。

---

<ブロッククオート

buildHeapには、2つのアプローチがあります。1つは ヒープの先頭 (配列の先頭) で siftUp を呼び出します。 を使用します。各ステップにおいて、以前にふるい分けられた項目 (前項目) は 配列の現在の項目）が有効なヒープを形成し、次の項目が はヒープ内の有効な位置に配置される。ふるい落とした後 各ノードで、すべてのアイテムがヒープ特性を満たす。第二の方法 逆に、配列の末尾から始めて、配列の末尾に移動します。 を前方に向かって後退させる。各反復で、アイテムを下にふるい落とす。 正しい位置に来るまで

配列aが5つの要素 a[4,2,3,5,6] を持っているとします。

シフトアップ -

input- a[4,2,3,5,6].

処理

配列の先頭から siftUp オペレーションを適用する。

siftUp(4) -
ルートなのでスワップなし

 heapified Array-a[4]

siftUp(2) -

親値(4)の方が大きいのでスワップなし

heapified Array-a[4,2]

siftUp(3) -

親値(4)の方が大きいのでスワップなし

heapified Array-a[4,2,3]

siftUp(5) -

の親値は2なので、(5,2)をスワップします。

          Array-a[4,5,3,2]

ここで、5の親の値は4なので、再び(5,4)をスワップします。

 heapified Array-a[5,4,3,2]

siftUp(6) -

まず、(6,4) の間を入れ替え、次に (6,5) の間を入れ替えます。

 heapified Array-a[6,5,3,2,4]

出力-a[6,5,3,2,4]です。

siftDown-

input- a[4,2,3,5,6].

処理中

配列の末尾から1つずつsiftDown処理を適用していきます。

siftDown(6) -

子プロセスを持たないので、スワップはできません。siftDown(5) と siftDown(3) も同様に、子プロセスを持たないので、さらに下へ移動することはできません。

今までの配列 - a[4,2,3,5,6] です。

siftDown(2) -

大きい方の子値と入れ替わります。ここでは6が大きい方なので、(2,6)をスワップします。

これで、配列は -a[4,6,3,5,2] となります。

siftDown(4) -

4は6と3の2つの子を持っているので、大きい方と入れ替えます。 これで Array は a[6,4,3,5,2] となります。

4は自分より大きい子、つまり5を持っているので、ここでもスワップが必要です。

配列は、- a[6,5,3,4,2] となります。

ヒープ化された配列 -a[6,5,3,4,2].

出力-a[6,5,3,4,2]です。

同じ要素のセットに対して siftUp と siftDown 操作を行うと、なぜ 2 つの異なる出力が得られるのでしょうか？または、同じ要素のセットにsiftUpとsiftDownが適用されたときに、異なるヒープを持つことが可能です。明確にお願いします :)

解決方法を教えてください。

はい、同じ要素のセットに対して異なるヒープを持つことは可能です。

どちらのアプローチでも、ヒーププロパティを満たすヒープが正しく生成されます。 親要素の値が子要素の値より大きいこと .

最初のアプローチ

    6
   / \
  5   3
 / \
2   4

2つ目のアプローチ

    6
   / \
  5   3
 / \
4   2

実際、手で描いてみると、例えば、他の可能なヒープがあります。

    6
   / \
  4   5
 / \
2   3

しかし、どちらのアプローチも正しい結果を生成しますが、複雑さが異なることに注意してください。参照 ヒープを構築する際の時間計算量がO(n)であるのはなぜか？ .