問題タブ [heap]

私が考えている次の問題があります（よく知られている/標準だと思います）：

バイナリ最小ヒープ内の k 個の最小要素のリストが O(k) であることを確認します。

BFSの大きな最小ヒープをトラバースして、単純なキューの代わりに最小ヒープを維持することを考えていました。最初は、補助最小ヒープには大きな最小ヒープのルートが含まれています。各ステップで最小値を抽出し、そのすべての子 (最大 2) を追加します。アルゴリズムは、補助最小ヒープで k 抽出分後に停止します。補助最小ヒープのサイズは O(k) です (抽出された最小キーごとに、その子を挿入します。最大 2)。

問題は、extract-min の複雑さが O(log k) であるため、このアルゴリズムの複雑さが O(k log k) であることです。そして、O(k) で 1 つを見つけなければなりません。

使用できるアイデア/論文はありますか?

ありがとう！

minmaxヒープアルゴリズムの実装を検索しています。この構造についていくつか覚えています。彼女の実装は1つのヒープ上にあります。ヒープツリーのレベル（フロア）でさえ最小の色で表示され、残りのノードは最大の色で表示されます。私はこれの動作のドラフトをいくつか覚えていますが、それに関するいくつかの良いドキュメントまたはいくつCかのC++コードスニペットを検索しています。Googleによる有用な情報を見つけることができません。これは広く普及していないアルゴリズムだと思います。

ご挨拶とお役に立ててありがとうございます。

私は現在、データ構造とアルゴリズムのクラスの割り当てに取り組んでいます。
指定されたヒープからノードを削除する必要があります。

私が持っている質問は、私が右、左にダウンヒープするのか、それとも重要なのかということです。

私の割り当てでは、ヒープを構築しています。ヒープのデータはファイルから取得されます。関数の 1 つはデータを取得することですが、ifstream read() 関数を理解するのに問題があり、これが原因でかなり厄介なエラーが発生しています。

私が受け取っているエラーは次のとおりです。

どんな助けでも大歓迎です！

私は現在、値が追加および削除されたときにヒープを表示するアプレットに取り組んでいます。ヒープを整数のツリー（IntTrees）として実装しています。スキューヒープのコードを書いていますが、「add」メソッドを使用すると問題が発生します。addメソッドは通常は機能しますが、値が追加されるとスタックオーバーフローエラーが発生することがあり、その理由がわかりません。

これが私がaddメソッドのために書いたコードです

「t」はインスタンス変数、つまりヒープ自体です。

このコードにスタックオーバーフローエラーを引き起こす何かがありますか、それともプログラムの他の場所に問題がありますか？ありがとう！

私の割り当てでは、出力する変数を返すヒープ削除関数を使用する必要があることを知っています。しかし、割り当ての要件は非常にあいまいであり、誰かが私にもっと良い説明をしてくれるかどうか興味がありました。2番目または3番目の引数の使用方法についてはかなり混乱しています。並べ替えが必要で、2つのforループが必要ですが、その後は迷子になります。課題の内容は次のとおりです。

この関数は、ヒープ構造からアイテムを取得し、それらをstdoutに出力します。ヒープ構造から単一のアイテムを取得するには、remove関数を呼び出します。この関数の最初の引数はヒープ構造のベクトル、2番目の引数はstdoutに割り当てられた印刷アイテムのサイズ、3番目の引数は1行の印刷アイテムの最大数、最後の引数は述語です。 。

これが私のコードです：

設定

intLevelsレベルとe要素 (両方ともint) を 2D 配列のObjects である heapArray に格納したヒープがあり、これはintLevels高さとMath.pow(2, intLevels)幅があります。仮説として、1、2、3、4、5、6、7、8、および 9 を入力するとします。ヒープは次のようになります。

一連のjava.util.Arrays.toString(Object[] a)s でそれを印刷すると、次のようになります。

この情報を取得して JTree を作成する方法を知っている人はいますか? 知らない人のために説明すると、JTree はリンクされたリストのように機能します。さらにノードを追加するルートノードがあり、それらにノードを追加できます。私が扱っていた唯一のヒープがこれだった場合、この方法でツリーを作成できることを私は知っています。

ツリーは次のようになります。

編集

答えのbuildTree(List<Object[]>)方法が実装されていることがわかりました：

まだ機能していないようです。ツリーは空のままです。

質問

この2D配列を特定の情報でJTreeにする比較的簡単で柔軟な方法を知っている人はいますか? 正しく実装されていれば、このツリー/ヒープ/配列に 1、2、3、4、5、6、7、8、および 9 を入力すると、上で示した具体的な方法と同じ結果になるはずです。

配列が最小ヒープかどうかを判断するアルゴリズムの概要を説明しようとしています。これに役立つドキュメントはありますか？Apache の Web サイトでその関数を見つけましたが、関数がどのように機能するかを正確に示していません。関数（BinaryHeap（boolean isMinHeap））が存在するだけです。

私はこれらの手順を持っています

実行すると正常にコンパイルされますが、実行が異常に停止した後、なぜ実行されているのですか? このコードを見て助けてください

ウィキペディアより。

100 セットの A オブジェクトがあり、各セットはクエリ ポイント Qi, に対応しています1 <= i <= 100。

アルゴリズムの反復ごとに、1 つのクエリ ポイント Qi を選択し、対応するセットから最小距離値を持つオブジェクトを抽出します。次に、100 セットすべてからこの特定のオブジェクトを見つけ、その ID で検索し、それらのオブジェクトをすべて削除する必要があります。

オブジェクトのセットごとにヒープを使用すると、オブジェクトを抽出するのにコストがかかりませんMIN(distance)。ただし、ヒープは距離値で編成されているため、id で検索しても他のヒープで同じオブジェクトを見つけることができません。さらに、ヒープの更新にはコストがかかります。

私が検討した別のオプションは、map<id, (distance, x, y)>for each セットを使用することです。このように ID による検索 (find 操作) は安価です。ただし、最小値を持つ要素を抽出するには線形時間がかかります (マップ内のすべての要素を調べる必要があります)。

必要な両方の操作に効率的な、使用できるデータ構造はありますか?

• extract_min(距離)
• 検索 (ID)

前もって感謝します！