問題タブ [binary-heap]

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

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

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

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

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

私の C++ データ構造クラスでは、ダイヤルアップ モデム シミュレータを実装しています。私たちの教授は、STL プライオリティ キューを使用する作業用ソース ファイルを提供してくれましたが、私たちの仕事は、バイナリ ヒープを実装することによってそれを置き換えることです。私は今日彼女に会いに行き、バイナリヒープとは何かについて助けてもらいましたが、彼女は基本的に私と私の友人にITに異動するように言いました:(.彼女は月曜日にプライオリティキューとバイナリヒープの両方について話し始めました。彼女は 1 時間で駆けつけました。今日はスライドが終わっていないので、新しい話題について話し始めたので、プログラムの期限である金曜日にバイナリ ヒープで再開する予定です。

ここまでは理解できましたが、バイナリヒープはプライオリティキューのバックエンドです。しかし、要素が挿入されているときやポップされているときにソートする必要がありますか? そして彼女はベクトルやリストを使用すると言いましたが、ツリーを構築しているとき、それはどこで機能しますか? また、このコードが彼女のコードで機能する理由もわかりません:

それが STL プライオリティ キューを宣言する方法ですか? プログラムは説明が難しいので、一番下に貼り付けておきます。ソースファイルは 1 つだけです。

注: Random.h には、統計分布に従って乱数を返す関数しかありません。

modemSimu.cpp:

ソートされた配列に裏打ちされた最小バイナリヒープとして優先キューを実装しようとしています。update_key関数を対数時間で実行しようとしていますが、これを行うには、配列内のアイテムの位置を知る必要があります。マップを使用せずにこれを行う方法はありますか？もしそうなら、どのように？ありがとうございました

ボトムアップヒープ構造は、（n + 1）が2の累乗であるという事実に完全に依存していませんか？（ここで、nはノードの数です）。

たとえば、n = 21の場合を考えてみましょう。（n +1）は2の累乗ではありません。これはどのように機能しますか？

最初に挿入（n + 1）/ 2ノード、つまり11ノードを作成します。次に、（n + 1）/ 4ノードを挿入して、前に挿入したノード、つまり5.5ノードの親にします。しかし、どうすれば「ノードの半分」を挿入できますか？nが2の累乗でない場合は常に、あるレベルでノード挿入の小数に到達します。これにどのように対処しますか？

残りのノードが2の累乗になるように一定量のノードを削除し、残りのノードからツリーを構築し、完了後に削除したノードをツリーにバブリングすることを検討しました。ただし、ノードの数が多い場合、これは実行不可能になります。つまり、ノードの数= 1600です。2の最も近い累乗は1024です。つまり、576ノードをバブルする必要があり、これには比較的時間がかかります。

Python の組み込みヒープ機能のいくつかを理解しようとしています。タプルのリストを渡すと、気に入らないようです (または、リストを正しく渡していない可能性が高い)。ここに私が持っているものがあります:

私が得るエラーは

TypeError: ヒープ引数はリストでなければなりません

私は何か間違ったことをしていますか？タプルのリストを渡す別の方法はありますか?

ありがとう！

誰でもこれで私を助けてください。プライオリティ キューを構築しようとしていますが、未解決の外部シンボル エラーが発生し続けます。どんな助けでも大歓迎です。

エラー 2 エラー LNK2019: 未解決の外部シンボル "public: __thiscall Node::Node(void)" (??0Node@@QAE@XZ) が関数 "public: __thiscall PriorityQueue::PriorityQueue(void)" で参照されています (??0PriorityQueue@ @QAE@XZ)

そのため、ユーザーがセットに追加する整数を「ヒープ化」することになっているプログラムに取り組んでいます。ただし、関数にパラメーターとして渡されたノードの左の子ノードにアクセスしようとすると、現在問題が発生しています。Visual Works のメモリが不足しています...

奇妙なことに、デバッガーでは、渡されたノードの Left 子ノードが作成され、渡されたノードに正しく割り当てられていることがわかります。しかし、ソース コードからアクセスしようとすると、クレイジーなメモリ エラーが発生します。

これが対応するコードです。うまくいけば、それは読みやすいです

呼び出されたときにエラーが発生した関数:

BinaryHeapNode クラスの 'left' のアクセサー メソッドは次のとおりです。

また、addLeftChildTo: メソッドを最初に呼び出すコードを参照すると役立つ場合があります...

私は何が間違っているのか理解できず、この問題で数時間立ち往生しています。何か案は？

かなり紛らわしい質問を投稿したので、最初から書き直しました...

これは実際には純粋に理論的な問題です。

たとえば、バイナリ ヒープがあるとします。ヒープを MaxHeap にすると、ルート ノードが最大の値を持ち、すべてのノードがその子よりも大きな値を持ちます。このヒープでは、「2 つのノードを交換する」、「2 つのノードを比較する」などの一般的な低レベルの操作を実行できます。

これらの低レベルの操作を使用して、通常の高レベルの再帰操作「シフトアップ」、「シフトダウン」を実装できます。

これらのふるい分けとふるい分けを使用して、「挿入」、「修復」、「更新」を実装できます。「更新」機能に興味があります。変更するノードの位置が既にあると仮定しましょう。したがって、更新機能は非常に単純です。

私の質問は: すべてのノードが値を new_values に変更し、その後、それらの位置が修正されるという方法で、より多くのノードを一度に更新できる、より高度な「更新」機能を作成することは (数学的に) 可能ですか? このようなもの：

この「double_update」でこれをいくつかテストしたところ、何も証明されていませんが、機能しました。

「トリプルアップデート」などはどうですか...

「マルチ更新」を使用して他のテストをいくつか行いました。そこでは、すべてのノードの値を変更してから { sift-up(); を呼び出しました。ふるいにかける(); ランダムな順序でそれぞれに 1 回。これはうまくいきませんでしたが、結果は正しくありませんでした。

これは役に立たないように聞こえますが、その背後にある理論に興味があります。そして、私がそれを機能させれば、実際には1つの用途があります.

私は答えを知っていると思います、そして最小の複雑さはO（nlogn）です。

しかし、 O（n）の複雑さ のヒープから二分探索木を作成する方法はありますか？

元の質問は、前日にアクセスされた 5 GB の URL を含むファイルが与えられ、上位 k の頻繁な URL を見つけます。この問題は、ハッシュ マップを使用して個別の URL の出現をカウントし、O(n log k) 時間かかる最小ヒープを使用して上位 k を見つけることで解決できます。

入力が (静的ファイルではなく) 無制限のオンライン データ ストリームである場合、どうすれば最終日の上位 k URL を知ることができるでしょうか?

または、最後の分、最後の日、および最後の時間の上位 k URL を動的に取得できるシステムに改善できる点はありますか?

ヒントをいただければ幸いです!!