問題タブ [min-heap]

私はソフトウェア開発者のインタビューの準備をしており、アルゴリズムの問​​題に取り組んでいます。私の本は、順序付けられていない配列を昇順でソートできる Heapsort アルゴリズムを示しています。最小ヒープでソートできるように変更しようとしています。しかし、コードのロジックに従うと、配列が正しくソートされません。私のコード (疑似コード) の何が問題になっていますか?

max-heapify を使用した本のヒープソート アルゴリズム:

min-heapify を使用して変更したコード:

最後の行を見てください。これは、priority_queue max_heap の初期化です。c++ const Compare& を無視する理由。だろうと思った

以下のように異なって見えますが、私は理解しています。

このページを読みました: http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

priority_queue コンストラクター パラダイムの決定的な定義を取得できません。

また、コンパレータとして「<」をオーバーロードすることがあるのはなぜですか。コンパレータとして「()」をオーバーロードすることがありますか? ありがとう

remove min 関数が呼び出されたら、Java で配列ベースの最小ヒープをどのように「ヒープ化」しますか (これは単にインデックス 1 の要素を取得して削除し、配列の最後の項目に置き換えます)。remove min が発生した後、配列を最小ヒープに戻す方法について混乱しています。

ヒープ最小配列では、インデックス 0 は常に空のままです。親インデックスは i/2、右の子は 2i + 1、左の子は 2i です。

どんな助けでも大歓迎です、ありがとう！

minheap を使用してプライオリティ キューを実装しようとしていますが、オブジェクトが間違った順序でキューから出てきます。私の直感では、問題はキュー内をふるいにかける方法にあるとわかりましたが、どこに問題があるのか​​ わかりません。誰かが私のアルゴリズムを見て、すぐに明らかな何か問題があるかどうかを確認できますか? 前もって感謝します。

ふるい落とす方法は次のとおりです。

そして、ふるいにかける方法は次のとおりです。

編集：

比較メソッドは次のように定義されます。

免責事項として、私はこのサイトを初めて使用するため、質問の仕方がよくわかりません。これらの概念のいくつかがどのように機能するかを理解しようとしているだけなので、あまり厳しくしないでください。最初の段階で理解できていない場合は、そこから始めて、残りの時間を無駄にしないように、そのことを教えてください。ここでは何も行きません。私の理解に問題があるのではないかと思うので、さまざまな領域でヒープがどのように機能するかについていくつか質問を投げかけ、それらに答えようとしました。

まず、空のヒープに追加されたランダムな数値のセットがどのように見えるかを理解する手助けをしたいと思います。たとえば、9、4、5、3、2、7、8、7 があるとします。それをヒープに追加した後、ヒープはどのようになりますか? これは視覚的に理解できます（と思います）9はルート、4は最初の左の子などですが、これは具体的にはツリーではなく、ヒープであるため、番号を切り替えてソートしますかそれらを（「私の理解が正しければ」の段落を参照）、最小または最大の順序でソートされるようにしますか？

ここで、ヒープから 9 を削除したとします (9 がルートになると思います)。この変更にどのように対応し、次に何がルートに入れられるのでしょうか? ここで、9 がルートの場合、次に大きい数字を取得して 9 のスロットにコピーしますが、これが最小ヒープであり、下部のノードを削除するだけの場合は、削除されるだけです。問題。

同様に、配列内のヒープ項目の親を取得する式は何になるでしょうか? -- これは理解できたと思います。親が i の場合、左の子は i*2 で右の子は i*2+1 になります。したがって、親を見つけるには、親を見つけるために i/2 を割る必要があります。たとえば、i=7 の場合、親は i=3 になります。これは、3.5 が切り捨てられるためです。また、i=6 の場合、親も i=3 になります。この例から、i = 7 の子は i = 3 の右の子になり、i=6 は i = 3 の左の子になります。

これについての私の理解が正しければ、新しい用語がルートに追加された後に再ヒープするには、子を親と比較し、子が大きい場合は用語を切り替えます。しかし、2 つの子 (2 つある場合) を比較して、どちらが大きいかを確認し、どちらを交換する必要があるかを判断する必要があります。これは最大ヒープの場合であり、最小ヒープの場合は逆になります。

最後に、ルート要素をどこに追加するとしたら、どのように再ヒープするのでしょうか?

この問題https://www.hackerrank.com/challenges/cut-the-treeを解決しようとするとき、 私は常に葉を選んで切り取り、その重みをそれが接続するノードに結合しようとしていました。PriorityQueue を使用してすべてのノードを格納し、隣接するノードのサイズを優先度として使用していました。しかし、いくつかのテスト ケースを試していると、優先キュー プロパティに違反しているように見えます。つまり、非リーフ ノードがリーフ ノードの前に表示される可能性があります。PriorityQueue は自動的に更新されますか、それとも更新する関数を呼び出す必要がありますか。私の一時的な解決策は、リストを使用してすべての葉を保存することです。

以下は私のコードです：

ありがとう。

私が問題を抱えているのは、buildHeap と buildMinHeap のものです。以前は、それらはまったくトリガーされませんでした。そのため、ソートされていない配列の場合、ノードが適切に印刷されるため、印刷部分が多かれ少なかれ機能するはずです。

現在、入力したデバッグ メッセージの一部を表示した後にプログラムがクラッシュするため、そこに無限ループがあると想定しています。何か案は？

編集:ああ、また、私はまだ学生なので、まだCに精通していません。いくつかのコンテキストを提供するだけです。

私のヒープは、幅の順に印刷され、羊を最も軽いものから最も重いもの (最小ヒープ) に並べ替えることになっています。私のテスト ファイルは 15 の羊を追加し、少なくとも 5 を削除する必要があります。範囲外の配列インデックスを取得しているため、削除部分をまだ試みていません。どんな助けでも大歓迎です。

ここに私のクラスがあります：