問題タブ [binomial-heap]

バイナリ ヒープは 2 つの子 (ツリー表現) しか持つことができず、二項ヒープは任意の数の子を持つことができるという構造の違いに関係なく、バイナリ ヒープと二項ヒープの主な違いを知る必要があります。

実際、最初の子が 1 つのノードに 2 番目に 2 番目に 2 番目に 4 番目にあるというように二項ツリー構造を編成する際に何が特別なのか疑問に思っています。

2 つの子を制限せずにヒープに通常のツリーを使用し、結合手順を適用して、1 つのヒープを他のヒープの左側の子にする場合はどうなるでしょうか。

私は最近、すでに書かれているいくつかのコードでプロジェクトを開始しました。彼の実装を調べることにしたところ、彼が単一リンク リストを使用してプライオリティ キューを実装していることがわかりました。

SLL についての私の理解では、リスト全体を反復処理する必要がある場合があるため、そのように実装するのは非効率的です。そのため、ヒープが好まれます。しかし、おそらく私はその背後にある何らかの理由を見逃しており、優先度キューにヒープではなく SLL を選択したことがある人がいるかどうか疑問に思っていましたか?

以下のテキストは、二項キューの記事からのものです。

左翼ヒープとスキュー ヒープの両方が、操作ごとに O(log n) 時間で効果的にマージ、挿入、および delete_min をサポートしますが、バイナリ ヒープは操作ごとに一定の平均時間で挿入をサポートすることがわかっているため、改善の余地があります。二項キューは、操作ごとに O(log n) の最悪の場合の時間で 3 つの操作すべてをサポートしますが、挿入には平均して一定の時間がかかります。

上記のテキストで、操作ごとの一定の平均時間とは、著者が何を意味するのですか? また、二項キューの挿入とはどのように異なり、平均して一定の時間がかかりますか?

操作ごとの一定の平均時間と一定の平均時間の違いは何ですか?

ここで二項キュー操作について読んでいます。

リンクの下部に、次のように記載されています

二項キューの実装

1. deletemin 操作には、ルートのすべてのサブツリーを見つける機能が必要です。したがって、各ノードの子が利用可能である必要があります（リンクされたリストなど）
2. deletemin では、サブツリーのサイズによって子を並べ替える必要があります。
3. 房を簡単にマージできるようにする必要があります。2 つの二項ツリーは、同じサイズの場合にのみマージできます。したがって、ツリーのサイズをルートに格納する必要があります。マージ中、ツリーの 1 つが他のツリーの最後の子になるため、各ノードの最後の子を追跡する必要があります。使用するのに適したデータ構造は、各ノードが次の形式の循環二重リンク リストです。

上記で、著者は「ランク番号」を意味しますか? 例を挙げて説明してください。

二項ヒープ構造では、最小ノードを指すポインターしかわかりませんが、任意のノードのキーを減らすにはどうすればよいですか? この場合、まず、このノードを見つけてから、O(lgN) 時間でスワップを実行する必要があります。

私はオンラインで検索し、ノードを減らす方法を多く指摘していますが、このノードにアクセスして減らす方法については言及していません。

編集：

ヒープの各ノードを指すポインターを使用する必要があります。

タイトルで言及されているものの中で、1つまたは別のヒープ実装を使用するかどうかをどのように決定すればよいか、誰かが私に説明してもらえますか?

問題に応じて、構造のパフォーマンスに関する実装を選択する際のガイドとなる回答が欲しいです。現在、優先キューを実行していますが、この場合に最も適切な実装だけでなく、他の状況で実装を選択できるようにする基本を知りたいです...

他に気になる点としては、今回は haskell を使っているので、この言語での実装を改善する裏技や何か知っていることがあれば教えてください! 以前と同様に、他の言語の使用に関するコメントも大歓迎です!

ありがとう！質問が基本的すぎる場合は申し訳ありませんが、私はヒープにまったく慣れていません。実装のタスクに直面するのはこれが初めてです...

再度、感謝します！

次の定義を持つクラスがあります。

私たちは大学で二項ヒープを学んでおり、マージと挿入のアルゴリズムをコードに実装しました。少なくとも、Visual Studio を一時停止して "Locals" に移動すると (マウスを変数の上に置いて)、期待どおりにデータが表示されます。

実験として、標準の「二項ノード」に 2 つの変数を追加しました。それらは x_point と y_point です。プログラムの実行中に、これが表示されます。

上で示した領域に注意してください。同じノードを表すはずですが、ご覧のとおり、x_point の値が異なります。(それ以外の場合は y_point が異なります)

なぜこれが起こっているのか、誰にも手がかりがありますか？私が理解しているように、それが同じノードを表す場合、データは同一である必要があります。しかし、そうではありません。つまり、同じノードではありません。どうすればそれが可能になりますか？「余分な」x_point 変数と y_point 変数を無視すると、コードは完全に実行されます。実際、私はこれが問題であることさえ知りませんでした。

私のスニペットからは見えませんが、クラス定義の外で編集する値は x_point と y_point だけです。他のものは公開されていますが、読み取り専用です。

編集：ここに私が作ったコードがあります、

フォーム ウィンドウを使用してユーザーからデータを取得し、ヒープに入力します。入力はこちら、

コードがあまり悪くないことを願っていますか？

私が知っているように、2 つのヒープをマージするために使用される二項ヒープまたはいわゆるマージ可能なヒープが存在します。私の質問は、これらのヒープを 1 つのヒープに動的にマージする代わりに、これら 2 つのヒープを 1 つの大きな配列にコピーしてからヒープ構築手順を実行すると、それは良いアプローチでしょうか?

ヒープ操作だけで2つのヒープを使用して1つのヒープを作成する方法がわからないためです。それが良い方法でないかどうか教えてください。または、可能であれば、マージ操作を伴う二項ヒープが実装されているリンクを教えてください。

グラフ実装の Vertex クラス内に handle というメンバーがあります。次のように宣言されます。

...ハンドルは、TA によって示された boost::heap ライブラリから取得されました。したがって、これが配置されている Graph.h ファイルには

このハンドル メンバーを使用するプログラムをコンパイルすると、次のエラーが発生します。

Graph.h:80: エラー: 予想される `;' 「ハンドル」の前に

すぐに、何が欠けているかを誰でも確認できますか (または、周囲の行をもっとよく見る必要がありますか?) ?

Purely Functional Data Structures (page 22)での Okasaki の実装は、2 つの部分でそれを行います。1 つはフォレストをマージし、もう 1 つはキャリーを伝播します。これは、ワンパスバージョンよりも分析が難しく、おそらく遅いと思います。何か不足していますか？

岡崎の実装：

すべてのキャリーを伝搬するコストの上限を証明する必要があるため、これを分析するのは難しいと思います (以下を参照)。私が思いついたトップダウン マージの実装は、明らかに O(log n) です。ここで、n はより大きなヒープのサイズです。

Okasaki の実装が O(log n) であることの証明: キャリーが「高価」(1 つまたは複数のリンクが必要) である場合、ゼロが生成されます。したがって、次の高価なキャリーは、そのポイントに到達すると停止します。そのため、すべてのキャリーを伝播するために必要なリンクの総数は、伝播前のバイナリ表現の全長程度以下であり、これは ceil(log n) によって上に制限されます。ここで、n はより大きなヒープのサイズです。