問題タブ [max-heap]

インオーダートラバーサルリストが与えられた場合、バイナリ最小/最大ヒープを作成するための最良の方法は何ですか？

私は次の構成に限定しようとしています：

1. バイナリヒープで使用される配列はありません。実装はノードベースです。 BinaryNode { value, parent, l_child, r_child }

2. Max-Heapに固執しましょう。

質問： BubbleDownを含む標準の挿入よりもうまくいくことができますか？

ヒープ データ構造について読んでいますが、いつ max heapify 関数を使用するのか、またその理由がわかりません。

ヒープを常に max-heap に保つ挿入関数を作成しましたが、max-heapify がいつ使用されるかわかりません。

説明していただけますか？ありがとうございました

これは私のコードです:

だから私はヒープを読んで、基本的な概念を理解しました。

しかし、実際にそれを実装する方法ではありません。

基本的に、私の問題は

1. 新しいノードを配置する場所をどのように知っていますか?

2. を削除するときに、ルートを置き換えるノードをどのように知ることができますか?

このコードは、本「アルゴリズム入門」に記載されています。このために、1つのインデックス付き配列を使用しました

この入力について

ideone.com では、「時間制限を超えました」と書かれています。Visual Studio でデバッガーを試してみたところ、次の結果が得られました。

なにが問題ですか？

次のような宿題の質問があります。

問題 1: 与えられた配列 [ 22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66 ] 配列の最大ヒープを構築します。詳細をスキップせずにすべての手順を表示します。

これは、インターネットでの調査からの max-heap に関する私の理解です。

最大ヒープは、親ノードが常に子ノードよりも大きく、「子を追加するたびに左側に追加して、ツリーが増加するたびに高さになるように、バイナリ ツリーでより簡単に表すことができる配列です。完全なツリーです」

とにかくこれは私が構築したものです

宿題の質問 2 を読むまでは、それが正しい答えだと思っていました。

問題 2: 問題 1 と同じ配列を使用して、Heapsort を使用して配列を並べ替えます。詳細をスキップせずにすべての手順を表示します。

今、私は混乱しています。多分私は問題番号2を答えました...

従来のHeapsortアルゴリズムは、ヒープの最後の要素を現在のヒープのルートと毎回スワップしheapification、プロセスを再び続行します。しかし、私はそれが一種の不要であることに気付きました。

サブ配列の の後heapification、ノードに最大値が含まれている間 ( の場合max-heap)、配列内の次の 2 つの要素は、現在と同じ順序で、またはそれらを交換して、並べ替えられた配列のルートに従う必要があります。それらが逆にソートされている場合。したがって、ルートを最後の要素と交換するだけでなく、最初の 3 つの要素 (ノードを含み、必要に応じて 2 番目と 3 番目の要素を交換した後) を最後の 3 つの要素と交換する方がよいのではないでしょうか。後続のheapifications(2 番目と 3 番目の要素の) は省かれますか?

この方法に不利な点はありますか (必要に応じて 2 番目と 3 番目の要素を交換することは簡単です)。そうでない場合、それが実際に優れている場合、パフォーマンスはどの程度向上しますか? 疑似コードは次のとおりです。

配列が であるとし[4,1,3,2,16,9,10,14,8,7]ます。を実行するheapifyと、 になり[16,14,10,8,7,9,3,2,4]ます。これで、heapsortの最初の繰り返しで 16 と 4 が入れ替わり、 になり[4,14,10,8,7,9,3,2,16]ます。これで新しいヒープのルートが[4,14,10,8,7,9,3,2]、うーん、ヒープされていない (14 と 10 はどちらも 4 より大きい) としてレンダリングされたので、別の実行を実行heapifyして を生成し[14,8,10,4,7,9,3,2]ます。これで 14 がルートになり、2 と交換して yield[2,8,10,4,7,9,3,14]になり、配列を currently にし[2,8,10,4,7,9,3,14,16]ます。ここでも 2 が非ヒープであることがわかります。そのため、再び a を実行するheapifyと、ヒープが になります[10,8,9,4,7,2,3]。次に、10 が 3 と交換され、配列が になり[3,8,9,4,7,2,3,10,14,16]ます。要点は、16 の前に 10 と 14 を格納するために 2 番目と 3 番目の s を実行する代わりにheapification、最初の s からわかるということです。heapification10 と 14 は 16 に続くため、2 番目と 3 番目に大きい要素です (またはその逆)。したがって、それらを比較した後 (既にソートされている場合は、14 が 10 より前になります)、そこにあるすべてを で交換し(16,14,10)、 (3,2,4)配列を作成し[3,2,4,8,7,9,16,14,10]ます。これにより、現在と比較して、さらに2つheapificationのsの後の状態と同様の状態になります。どちらもさらに が必要になりますが、2 番目の方法では、2 つの要素 (14 と 10) を比較するだけで、この時点に直接到達できます。[3,8,9,4,7,2,3,10,14,16][3,2,4,8,7,9,16,14,10]heapification

重複の可能性:
Python での最大ヒープの実装には何を使用しますか?

Python の heapq を何らかの方法で実装しようとしていますが、max-heap 用です。解決策は、(-1) と複数のキューを使用することですが、ヒープに URL を保存する必要があるため、これは役に立ちません。したがって、最大値をポップできる最大ヒープが必要です。

これまでのヒープソートプログラムは次のとおりです。

maxheapify 関数では、左または右の子にヒープ化するかどうかを決定するために、2 つの比較が行われます。最悪の場合、これはツリーの高さ ( lg(n) ) の 2 倍の比較を行うことを意味します。これは、maxheapify のコストが 2*lg(n) であることを意味します。maxheapify を変更して、約 1*lg(n) しか必要としないようにするにはどうすればよいですか?

バイナリサーチを再帰的に使用できるというヒントを得ましたが、その方法についてはまったく手がかりがありません。

ヘルプ/洞察に感謝します！

配列を使用して要素を格納する MaxPQ ヒープがあります。ヒープ内の特定の要素を見つけるために使用できるアルゴリズムは何ですか? 私が現在使用しているアルゴリズムは、インデックス 1 から始まり、ヒープに追加された要素の数まで、配列を反復処理します。このアルゴリズムの複雑さは O(N) ですが、複雑さ O(logN) のアルゴリズムはありますか?

サイズ10の整数配列があります。実行した完全な二分木を描画する必要があります。次に、siftupプロシージャを使用して他の3つの要素を挿入する必要があります。各挿入に続く最大ヒープを表示します。

各挿入後の最大ヒープが何を示しているのかわかりません。つまり、1つの要素を挿入するたびに、最大ヒープのサイズを表示する必要がありますか？

定義（最大ヒープ）HEAP（X）Xを全順序集合とします。Xのヒープは、空の∅であるか、完全な二分木tであり、各ノードにnt≥1ノードで構成され、各ノードに次のようにXの値が割り当てられます。ノードiの値≤ノードiの親の値、i = 2,3、...、nt。ヒープのサイズは、ツリー内のノードの数です。サイズが0の場合に限り、ヒープは空になります。

最大ヒープの定義はこのようなものですが、私には少しあいまいに見えます。