問題タブ [min-heap]

カスタム比較関数を定義して、オブジェクトのセットを最小ヒープに格納したいと思います。Pythonディストリビューションの一部として利用可能なheapqモジュールがあるようです。このモジュールでカスタムコンパレータを使用する方法はありますか？そうでない場合は、他の誰かがカスタムの最小ヒープを構築しましたか？

作成した構造体型の最小ヒープをC++で実装しようとしています。このタイプのベクトルを作成しましたが、make_heapを使用するとクラッシュしました。これは、ヒープ内のアイテムを比較する方法がわからないため、理解できます。構造体タイプの最小ヒープ（つまり、最上位の要素は常にヒープ内で最小の要素）を作成するにはどうすればよいですか？

構造体は以下のとおりです。

ランクメンバーを使用してDOC構造を比較したいと思います。どうすればいいですか？

コンパレータクラスで優先度付きキューを使用しようとしましたが、それもクラッシュしました。また、本当に必要なのがヒープである場合に、基礎としてヒープを使用するデータ構造を使用するのもばかげているようです。

どうもありがとうございました、bsg

バイナリ ヒープから最小値を抽出しようとしていますが、うまくいきません。ここに私のBubbleDownコードがあります:

いくつかの数字だけを交換しているように見えますが、すべてではありません。理由がわかりません。私はそれを別の方法で再コーディングしようとしましたが、すでに何度も...

私は何を間違っていますか？

私が理解しているように、ユーザー定義の構造体の場合は簡単です。演算子 < をオーバーロードするだけです。ただし、int/float などの場合、int の演算子 < をオーバーロードする必要はありますか? これが私が試したものです：

結果は次のとおりです。

今 pop_heap、push_heap は最小ヒープを正しく維持しませんか? これを達成する簡単な方法はありますか？ありがとう！

編集：申し訳ありませんが、マニュアルを注意深く確認していませんでした。はい、comp を pop_heap または push_heap に渡すとうまくいくはずです。しかし、外部コンパレータを使用しないでくださいとはどういう意味ですか? それが正しい方法ではない場合、これを達成するための一般的な方法は何ですか?

インオーダートラバーサルリストが与えられた場合、バイナリ最小/最大ヒープを作成するための最良の方法は何ですか？

私は次の構成に限定しようとしています：

1. バイナリヒープで使用される配列はありません。実装はノードベースです。 BinaryNode { value, parent, l_child, r_child }

2. Max-Heapに固執しましょう。

質問： BubbleDownを含む標準の挿入よりもうまくいくことができますか？

これはウェブサイトです

ページの半分を少し下った辺りで、彼はこのボグルと呼ばれるゲームを解くための疑似コードを提示し始めます。私は彼がこの文で何を意味しているのか混乱しています

• が であるかどうかを確認します。その場合currentletterは、新しい文字を含むにq挿入し、同じ座標とポインター メンバーを とします。nextheapucurrentletter

• currentletter:*の痕跡を復元します

q誰かが何を明確にしu、そのチェックが何を達成しようとしているのかを明確にしていただければ幸いです。

私は以下の構造体を持っています

この構造体のオブジェクトがいくつかあります。ここで、これらのオブジェクトをSTLの優先キューに挿入して、優先キューがアイテムをカウント順に並べ替えるようにします。そうする方法について何かアイデアはありますか？最小ヒープが好ましい。構造体ではなく、プリミティブデータ型に対して上記を行う方法を知っています

Javaで最小ヒープを実装しようとしていますが、要素の挿入と削除（最後に挿入、ルートを最小として削除）に問題があります。ほとんどの部分で機能しているようです（私はプログラムを使用してヒープを視覚的に表示し、minが削除されたときに新しいルートを出力しています）。

私の問題は、何らかの理由で、新しいアイテムが追加されたときにルートが新しいアイテムに切り替わらないことですが、その理由はまったくわかりません。また、これは重複が多い場合にのみ問題になるようです。ヒープは完全に正常に機能していないようです（親は子よりも小さい）。ほとんどの場合、そうです。たまにそうではなく、私にはランダムに見えます。

これはジェネリックで行われ、基本的にほとんどのアルゴリズムに従います。私が事実について知っている他のすべてはうまくいきます、それは間違いなくこれらの2つの方法の問題です。

メソッドで宣言されていない変数はすべてグローバルであり、現在/最後/一時的な状況全体が追加されるなど、いくつかのことがおそらく冗長であることを知っているので、申し訳ありません。私はすべての名前を自明にし、removeMinで行ったすべてのチェックを説明しようとしました。どんな助けでもめちゃくちゃに感謝されるでしょう、私は物事を調べてデバッグすることができる限り私は得ました。私はここで根本的に何かが欠けていると思います。

CLRSを読んでいて、6.5-8の演習で問題が発生しました。

O（n lg k）時間アルゴリズムを指定して、k個のソート済みリストを1つのソート済みリストにマージします。ここで、nはすべての入力リストの要素の総数です。（ヒント：k-wayマージにはmin0heapを使用してください。）

解決策は、誰もが言うように、

1）kリストの最初の要素を使用してk要素の最小ヒープを構築します。

2）extract-min（）を使用してヒープから最小の要素を取得し、結果リストに追加します。

3）ヒープから抽出したものと同じリストから次の要素を選択します。それをヒープに挿入し、2）に進みます。

時間はO（n lg k）であることは理解できますが、ステップ3）での選択の正しさはわかりません。当たり前のようですが、正式な証明はありますか？

フレデリクソンのヒープ選択アルゴリズムの簡単な説明はありますか? そうでない場合、アルゴリズムの根幹を説明できる人はいますか?