宿題で困っています。C++ でヒープを使用してプライオリティ キューを実装するように依頼されました。

ヒープを作成するためのコード例を検索しているときに、この定義に何度も遭遇しました。

ヒープを表す配列Aは、次の 2 つの属性を持つ配列です。

– length、配列内の要素の数

– heap-size、配列に格納されているヒープ要素の数

だから私の質問はこれです: Aとは何ですか? 自分で実装する必要がありますか (要素の配列、長さ、heap_size の 3 つのフィールドを保持するクラス ヒープを作成するとします)。

どうやって始めたらいいのかわからない。

背景

ウィキペディアや私が見つけた他の情報源によると、空のバイナリヒープから始めてn個の要素を挿入することでn個の要素のバイナリヒープを構築するのはO（n log n）です。これは、バイナリヒープの挿入がO（log n）だからです。そしてあなたはそれをn回やっています。これを挿入アルゴリズムと呼びましょう。

また、要素の前半/上半分をシンク/トリクルダウン/パーコレーションダウン/カスケードダウン/ヒープダウン/バブルダウンする別のアプローチも示します。これは、中央の要素から始まり、最初の要素で終わります。 O（n）、はるかに優れた複雑さ。この複雑さの証拠は、各要素のシンクの複雑さがバイナリヒープ内の高さに依存するという洞察に基づいています。それが下部に近い場合、それは小さく、おそらくゼロになります。上部に近い場合は、大きくなる可能性があります。おそらくlognです。重要なのは、このプロセスで沈められたすべての要素の複雑さがlog nではないため、全体的な複雑さはO（ n log n ）よりもはるかに小さく、実際にはO（n）。これをシンクアルゴリズムと呼びましょう。

質問

同じ理由で、挿入アルゴリズムの複雑さがシンクアルゴリズムの複雑さと同じではないのはなぜですか？

挿入アルゴリズムの最初のいくつかの要素に対して行われた実際の作業を検討してください。最初の挿入のコストはlognではなく、ゼロです。これは、バイナリヒープが空であるためです。2番目の挿入のコストは最悪の場合1スワップであり、4番目の挿入のコストは最悪の場合2スワップであり、以下同様です。要素を挿入する実際の複雑さは、バイナリヒープの現在の深さに依存するため、ほとんどの挿入の複雑さはO（log n ）未満です。n個の要素がすべて挿入されるまで、挿入コストは技術的にはO（log n）に達しません[最後の要素の場合はO（log（ n -1））です]。

これらの節約は、シンクアルゴリズムによって得られる節約と同じように聞こえますが、なぜ両方のアルゴリズムで同じようにカウントされないのでしょうか。

配列とリンクリストを使用してバイナリヒープの実装を比較しようとしています。すべての操作が連結リストを使用した操作と同等かそれ以上に高速に実行できるため、あらゆる点で配列の方が優れていると思います。また、必要なメモリも少なくなります。

しかし、リンクされたリストを使用する方がバイナリ ヒープの配列よりも優れている理由はありますか?

私の関数 somethingWrong() とオーバーロード演算子をチェックしてもらえますか。関数 somethingwrong() を実行すると、「True」と「False」が返されることがあります。私は何も変えていません。なぜこれが起こっているのですか?

これは、私が取り組んでいるダイクストラ アルゴリズム グラフです。

ありがとうございました

main.cpp:

グラフ.h

// 最小ヒープ データ構造

(最大) ヒープでは、O(1)時間内に最大のアイテムを見つけるのは簡単ですが、実際にそれを削除するには、 の複雑さが必要ですO(log(n))。

では、ヒープへの挿入と削除の両方O(log(n))が .

現在、バイナリ ツリー構造上に実装された Java でバイナリ ヒープを作成しようとしています。要素を追加した後にツリーを「ヒープ化」する方法をよく理解していますが、占有されていない最初のリーフを見つけるためのロジックはヒープの一番下で私を逃れます。

占有されていない最初のリーフを見つけることは、幅優先のトラバーサルであると想定されていることは承知していますが、幅優先のトラバーサル アルゴリズムがどのように機能するかはまだわかりません。

バイナリ ツリー上に実装されたバイナリ ヒープを作成しようとしていますが、ヒープの「下部」、つまりツリーの最初のヌル スペースに新しいノードを追加する方法を見つけるのに苦労しています。最初のトラバース。ヒープ化機能は既に動作していますが、ヒープ化する前に新しいノードを追加する方法がわかりません。

ノードを追加できるヌル空間を見つけることができる一貫したアルゴリズムを考えることができないようです。何かを思いつくたびに、うまくいきません。私は何をしますか？

ヒープは常に完全な二分木であることを知っています。しかし、いつヒープが完全な二分木になるのだろうか? ヒープが常に完全な二分木になるためには、どのような条件が必要ですか?

来週の試験では、BinaryTree、BinarySearchTree、および BinaryHeap を構築する方法を学ばなければなりません。唯一の問題は、Web 上のほとんどの例が単純すぎて理解できないことです。それらは、ドキュメントのない単なるコードの集まりです。3 つのデータ構造を構築する簡単な例を探しています。関数のドキュメントを含む例について考えてみてください。すべてがどのように機能するか。3 つのデータ構造の優れたチュートリアルを知っている人、または私にとって良い例を持っている人はいますか?