algorithm - 次の要素を順番に挿入してヒープを作成します

Question

質問：

次の要素を指定された順序で挿入して、ヒープを作成します。挿入と細流化のたびにヒープを表示します。（ヒープは、最高のキー値を一番上に保つように実装する必要があります。）

5 4 6 7 9 8 1 2 3

ヒープの作成が完了したら、ヒープから各要素を削除します。削除して細流化するたびにヒープを表示します。各ステップで削除された要素を示します。

要素をヒープに挿入する方法は知っていますが、作成する方法はありますか？そして、ヒープから要素を削除する方法が本当にわかりません。

Answer 1

答えにはバイナリ ヒープを想定します。多くの異なるヒープがありますが、これは宿題のように聞こえ、かなり基本的な質問であるため、そこにある最も基本的なヒープについて説明します。

まず、ヒープは空です。

次に 5 を挿入すると、ヒープは次のようになります。

5

次に、一番下に 4 を挿入します。4 は 5 よりも小さいため、親との位置を変更しません。ヒープは次のとおりです。

   5
  /
 4

次に、5 の下に 6 を挿入します (常に左から右に挿入します)。新しく挿入されたノード (6) の値をその親 (5) と比較し、ヒープ プロパティに違反しないように、それらを交換する必要があることに気付きます。

   6
  / \
 4   5

ここで、次の使用可能な場所 (4 の下) に 7 を挿入し、7 > 4 であるため、その親と交換します。次に、7 > 6 として再び交換 (または細流化) し、次を取得します。

    7
   / \
  6   5
 /
4

等々...