サイズ10の整数配列があります。実行した完全な二分木を描画する必要があります。次に、siftupプロシージャを使用して他の3つの要素を挿入する必要があります。各挿入に続く最大ヒープを表示します。
各挿入後の最大ヒープが何を示しているのかわかりません。つまり、1つの要素を挿入するたびに、最大ヒープのサイズを表示する必要がありますか？
定義（最大ヒープ）HEAP（X）Xを全順序集合とします。Xのヒープは、空の∅であるか、完全な二分木tであり、各ノードにnt≥1ノードで構成され、各ノードに次のようにXの値が割り当てられます。ノードiの値≤ノードiの親の値、i = 2,3、...、nt。ヒープのサイズは、ツリー内のノードの数です。サイズが0の場合に限り、ヒープは空になります。
最大ヒープの定義はこのようなものですが、私には少しあいまいに見えます。
各挿入の後に、結果のツリーを表示する必要があります。つまり、最初にヒープがある場合
3
/ \
1 2
そして、5を挿入すると、最後のヒープ位置から始まり、ヒープヘッドまでバブルアップします。
3 5
/ \ / \
1 2 => 3 2
/ /
5 1
同様に、4を挿入すると、次のようになります。
5 5
/ \ / \
3 2 => 4 2
/ \ / \
1 4 1 3
簡単に言うと、最大ヒープは、親の値がその子の値よりも大きいヒープです。最初の完全な二分木を描いたとき、それはすでに最大ヒープの形になっていますか？ふるい分け（私の大学ではバブルアップと呼んでいましたが、要点以外に）は、このようなスレッドで説明するのが少し複雑なので、@DanteisnotaGeekに同意します。ウィキペディアの記事には、ふるい分け手順がどのように機能するかについての優れた図があります。挿入後に最大ヒープを表示するには、各挿入後に最大ヒーププロパティを満たすようにバイナリツリーを描画するように求められます。したがって、最終的には、最初のツリー、最初の挿入、2番目の挿入、および3番目の挿入を含むツリー、つまり合計4つのツリーが必要になります。
ヒープでは、いつでも、ルートノードからリーフノードまでが順序付けられ、線形になります。
ヒープ内の次のスロットに要素を挿入すると、行の順序が変更されます。
したがって、挿入の最後のステップは、線形データ構造の並べ替えになります。バブルソート