問題タブ [min-heap]

最小ヒープ内の最大アイテムが N 個のアイテムを持つツリーの葉の 1 つになければならないことを証明するにはどうすればよいですか?

最小ヒープの全体的な設計を理解しており、最大アイテムがリーフの 1 つにあることを示す/図を描くことができます (深さ N + 1 のノード > 深さ N のノード)。証明をどのようにフォーマットすればよいかわかりません。

私がやろうとしていることは明らかだと思いますが、私はジェネリックの専門家ではありません.

コンパイル時に警告が表示されます。

わかりません。私は何が欠けていますか？

最初は、 this.get(i) と this.get(parent) が Comparable のインスタンスであることを確認する必要があると考えていたので、チェックを追加しました。

しかし、それは同じ警告を出します。

現在、グラフ全体でダイクストラのアルゴリズムを実行し、元のノードからの合計距離によってノードの最小ヒープを形成しています。次に、ヒープから上位 n 個の要素を削除します。

これは非常に非効率的だと思います。最も近い 10 個のノードを見つける必要があり、グラフに 100000 を超えるノードがあるとします。次に、グラフ全体でダイクストラを実行するのは時間の無駄のようです。しかし、問題は、グラフ内のすべてのノードへの最短パスを計算せずに、上位 10 個の最も近いノードを見つけることができる他の方法がわからないことです。

より良い方法はありますか？

あるインタビューでこの質問をされたことがあります。私は主に、O(n^2) よりも優れた時間で 2 次元配列をトレースするソリューションを提供することに行き詰まりました。質問は次のとおりです。

これが私が与えた答えです：

どうやら (私が彼の期待する解決策を示していたとしたら) 2 次元配列内の個々の配列が既にソートされているという仮定を利用していたでしょう。上記の解決策は、私のインタビュアーを納得させませんでした。

では、上記のクラスを O(n^2) よりも効率的な方法で使用して、期待される出力を生成するにはどうすればよいでしょうか?

PS: A) サンプル入力内の個々の配列は常にソートされることに注意してください。B) 入力には重複があり、出力には重複が含まれている必要があります。

プロセスの各段階を示す次のリストから示されるヒープの作成をトレースします。

a. {5, 13, 2, 25, 7, 17, 20, 8, 4} 分のヒープ

私はこれを正しくやっているといいのですが。次の問題に進む前に、これが正しいかどうかを確認したいと思いました。コメントやヘルプをいただければ幸いです。

minHeap クラスを実装したので、コードを変更せずに minHeap クラスを最大ヒープとして使用できるかどうか興味がありますか?