問題タブ [binary-heap]

すでに n 個の要素を含むバイナリ ヒープに k 個の新しい要素を挿入する時間の計算量はどれくらいですか? k 個の要素を 0(k + Log n) の複雑さで挿入する必要があるという制約があります。

ヒント: ヒープ構築と同様のボトムアップ アプローチを使用します。

と呼ばれる構造体を作成しましたが、Nodeその構造体へのポインタを Phobos のエントリとして使用できるようにしたいと考えていますBinaryHeap。ただし、構造体へのポインターに対して (または実際には一般的に) どのように実装されてopEqualsいるかはわかりません。opCmp私は、ドキュメントで私を助けるものを見つけることができませんでした。誰かが私を正しい方向に向けることができますか?

C++ で独自のライブラリを作成しようとしており、ヒープ データ構造を実装したいと考えています。

ヒープの挿入、削除、検索のすべてのアルゴリズムをすでにコーディングしました

必要なのは、ヒープを保持するコンテナーです。

それらが配列として実装されていることは知っていますが、配列は一定のサイズである必要があり、メモリを何度も再割り当てするのは好きではないためです。vectorヒープのコンテナーとして使用する必要がありますか?

私は自分自身を実装しvectorました。

Java で二分木からヒープを作成しています。私の実装は次のようになります。

ここで、ノードの n 番目の要素を取得したいと考えています。n をバイナリ文字列に変換し、最初の 1 をポップしてから、0 ごとに左に、1 ごとに右に移動するのが賢明だと思いました。

root.left.left.rightそれはそれほど難しくないように思えますが、今私の問題は、 9 番目の要素に到達するような出力をどのように作成するかです。コピーを取得したいだけではなく、簡単です (以下のgetNode(int n)関数を参照)。そのノードへの参照が必要なので、たとえばその場所に新しいノードを追加できます。

それはJavaでも可能ですか？Python では".left.left.right"String を作成して を使用するだけrunですが、Java ではそれができないようです。

これは、私が最近遭遇したインタビューの質問の 1 つです。

完全またはほぼ完全なバイナリ ツリーのルート アドレスが与えられた場合、ツリーを最大ヒープに変換する関数を作成する必要があります。

ここには配列は含まれていません。ツリーはすでに構築されています。

たとえば、

出力として可能な最大ヒープのいずれかを持つことができます--

また

等...

私は解決策を書きましたが、前後のトラバーサルの組み合わせを使用しましたが、それは O(n^2) で実行されると思います。私のコードは次の出力を提供します。

私はより良い解決策を探していました。誰か助けてくれませんか？

編集 ：

マイコード