問題タブ [min-heap]

最小ヒープ内の 2 つのノード間の最短パスを見つけるために、小さなスニペットを作成しました。

より良い平均的なケースでこれを行うより良い方法はありますか? ただ学ぶ。

編集：

簡単にするために、この配列がバイナリ ヒープであるとしましょう。ルートは 1 で、たとえば 5 と 7 の間の最短パスは shortestPath(5, 7) で与えられます。

このコードは、バイナリ ツリーが最小ヒープかどうかを調べるためのものですNullPointerException。パブリック スタティック ブール値 isMinHeap の 3 番目の if ステートメントで引き続き発生します。コードが有効だと思っていたので、なぜこの例外が発生し続けるのかわかりません上記の休憩のため。

HashSet をサイズ順に並べる優先キューを実装しようとしています (つまり、最小の HashSet が最高の優先度になります)。

Javaでこれを実装するにはどうすればよいですか?

以下は、HashSets を優先度番号 (最初に高いもの) で正常に並べ替える私の試みです。

私の主な方法：

私のPriorityQueueクラス

バイナリ ヒープにフロートを設定したい。具体的には、最小ヒープを実装したい。

フロートはサポートOrdされていないようで、そのままでは使用できません。それらをラップする私の試みは、これまでのところ失敗しています。ただし、それらをラップできれば、最小ヒープOrdを効果的に作成するような方法で実装することもできるようです。BinaryHeap

私が試したラッパーの例を次に示します。

問題はpop、それが最大ヒープであるかのように値を返すことです。

最小ヒープとして値を入力するBinaryHeapには、正確に何をする必要がありますか?f64

次の例を考えてみましょう。乱数を最小ヒープに追加し、同時に同じ番号を同じ順序で最大ヒープに追加しています。したがって、最後に、これらの 2 つのヒープの数値は同じになりますが、1 つが最小ヒープで、2 つ目が最大ヒープです。

ここで質問です：

最大ヒープから最大要素を削除することにした場合、最大ヒープからのその最大要素は常に最小ヒープの一番下にありますか? そうでない場合、別の質問は、その最大要素を最小ヒープの最後の要素と交換して最小ヒープから削除したい場合、最後の要素を削除する場合、その切り替えられた要素を比較する必要がある操作を実行する必要があるかどうかです。最小ヒープを修復するために彼の子供と一緒に？それとも、最小ヒープを修正するために親と比較することが常に当てはまりますか?

アーク型のオブジェクトを作成し、それをヒープに挿入します。ヒープはそれらを昇順でソートする必要がありますが、出力は機能しません

しかし、それは私にこれを与えます

これはアーククラスです

これは最小ヒープクラスです

min-heap のインプレース アルゴリズムを実装しようとしています。BST を並べ替えられたリンク リストに変換しました。以下はコード スニペットです。

}

デバッグ後、適切な出力が得られますが、順不同でトラバースしているときに、スタック オーバーフロー例外が発生します。