問題タブ [max-heap]

重複の可能性:
最大ヒープから k 番目に大きい要素を O(k) 時間で見つけるにはどうすればよいですか?

与えられた最大ヒープがあり、k 番目に小さい要素が任意の与えられた数よりも大きいかどうかをチェックするために、o(k) 時間の複雑さでアルゴリズムを見つけたいと考えています。

最大ヒープ内の最小の整数を削除する関数 HEAP-DELETE-MIN(Array) を実装する必要があります。私は関数自体を求めているわけではありませんが、誰かが 私が始めるのを助けるためにいくつかの疑似コードを提供してくれませんか? それは大きな助けになるでしょう。配列は、関数の最後に最大ヒープのままにする必要があります。

minHeapクラスをmaxHeapクラスに変換しようとしています。minHeapクラスのコードが与えられました。その1つのメソッドはaddでした。次のようになります。

最初のノードは自動的にnullに設定されるため、追加されるものはすべてノード1以降に配置されます。すでに述べたように、このコードはminHeap構造を与えます。したがって、maxHeapに変更します。コンパレータの符号を次のように反転します。

入力している項目は整数値で格納されています。挿入順に次のとおりです。

minHeap構造では、これらは次のようにノードに格納されます。

maxHeap構造では、符号を変更すると次のように格納されます。

minHeap構造体の場合と同じ種類の順次順序ではなくなったことに注意してください。これは重要ですか、それともまだ有効なmaxHeapですか？

木のような構造を見せようとした私のひどい試みについてお詫びします。

現在、最大ヒープを実行しています。remove() メソッドを使用すると、より大きな子と交換することを理解しています。両方の子の優先順位が同じ場合はどうなりますか? 例えば

ケース 1:

ヒープ = [5,7,7,16,15]

5 を削除して 15 に置き換えると、右側に滴り落ちるので (これは間違っています)、左側に滴り落ちます。

しかし、私が持っている場合、同じロジックを使用して

ヒープ = [5,7,7,16,15,18]

左に垂れ下がると、有効なヒープではなくなります。

有効なヒープを確保するにはどうすればよいですか?

最大 1 つのスワップでヒープへの挿入を実行するアルゴリズムはありますか (O(log n) の比較が許可されます)

Udi Manber 著の有名な本「Introduction to Algorithms」には、次のような質問があります。

アルゴリズム *Insert_To_Heap* はヒープを何度もスワップする可能性があります。多くても 1 つのスワップが実行されるようにアルゴリズムを変更します。O(log n) の比較は引き続き許可されます。

私はそのようなアルゴリズムを考えることはできず、不可能だとさえ思います(最大要素を最大ヒープに挿入した場合、それはまったく機能しないようです)。これは不可能であると述べている回答もあります.しかし、この質問が良い情報源からのものであることを考えると、私はもう一度尋ねます.

最大ヒープ O(n) を作成する時間の複雑さはどうですか。子ノードがその親と比較するのは O(i) だけですか、それとも O(log n) ですか。