問題タブ [fibonacci-heap]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
1 に答える
879 参照

java - Dijkstra の Shortest Path Java 実装で既存の Fibonacci Heap Java 実装を使用する

Javaプログラミング言語を使用して、正のエッジコストを持つグラフに最も効率的な最短経路アルゴリズムを実装しようとしています. 私の知る限りでは、これは優先キューとしてフィボナッチ ヒープを使用したダイクストラのアルゴリズムです。リンクに記載されているように、Keith Schwarz による次の Fibonacci Heap 実装を借りました。http://keithschwarz.com/interesting/code/?dir=fibonacci-heap

私のコードでは、この質問で提示されたダイクストラ アルゴリズムの実装も変更しました。

Java: ダイクストラのアルゴリズムを実装するためのフィボナッチ ヒープの使用

これが私の実装に基づく更新されたダイクストラです。

これが私の Node と AdjacentNode クラスです。

次の行でキーを減らしたいと思うまで、すべてうまくいきました。

私が直面している問題はvEntry、ヒープ内に既に存在するノードでなければならないということです。ただし、このノードをヒープから取得することはできません。これは、隣接するノードを取得するために考えられる唯一の方法はv、 node の隣接リストを使用することであるためuです。しかし、次の行では、それを新しい Entry Node として誤って表現しています。

ただし、これにより、探しているノードを持つヒープに存在するエントリではなく、探しているノードを保持する新しいエントリが作成されます。これにより、予想どおり Null ポインター例外が発生します。

この問題の解決策がわかりません。このヒープ実装では、特定のノード エントリに隣接するノード エントリを取得することはできないようですか? 誰か助けてくれませんか?ありがとうございました。

0 投票する
1 に答える
809 参照

amortized-analysis - フィボナッチ ヒープの償却分析を行う理由

すべての操作分析のフィボナッチ ヒープでは、本質的に償却されます。二項ヒープの場合のように、通常の分析ができないのはなぜですか。

0 投票する
2 に答える
223 参照

java - FibonacciHeap は最小ヒープですか? フィボナッチヒープを使用して最大を見つける方法は?

私の Java プロジェクトは、Max Fibonacci ヒープを使用して、上位 n 番目に人気のあるハッシュタグを見つけることです。レコードは次のようになります。

しかし、フィボナッチ ヒープには find min 関数しかありません。「フィボナッチ ヒープ」、「最小フィボナッチ ヒープ」、「最大フィボナッチ ヒープ」の違いは何ですか?

私の考えは、関数 extractmax() を n 回使用して上位 n を取得することです。しかし、マックス フィボナッチ ヒープとは何かわかりません。

0 投票する
0 に答える
74 参照

data-structures - フィボナッチヒープの「n」個の最大要素を見つけるにはどうすればよいですか?

最大フィボナッチ ヒープは、構造体の最大要素への 1 つのポインターを持つことができます。しかし、これらの「n」を見つけるにはどうすればよいでしょうか? のように、現在の要素の次の最大要素を見つけるにはどうすればよいですか?

1 つの注意点は、異なる最大要素数に対して構造が再度クエリされる可能性があるため、構造から要素を削除できないことです。たとえば、上位 3 つの要素を 1 回要求された後、上位 5 つの要素について照会される場合があります。

それとも、削除して再挿入する必要がありますか? その場合、最大要素をスタック/キューに格納し、クエリを提供したらそれらを再挿入する方がよいでしょうか? また、これはツリーの構造を変更しませんか?

0 投票する
0 に答える
355 参照

algorithm - フィボナッチヒープがプリムのアルゴリズムの効率をどのように向上させるか

Prim のアルゴリズムとフィボナッチ ヒープは知っていますが、私の質問は、フィボナッチ ヒープが配列リスト ベースの最小優先度キューの実装よりもアルゴリズムの効率を向上させる方法です。

0 投票する
1 に答える
65 参照

c++ - c++でクラスを再帰的に呼び出す方法は?

こんにちはこれはコードです:

クラス「エントリ」では、エントリを再帰的に呼び出したいので、次を使用できます。

これが Java で機能することはわかっていますが、これを C++ でコンパイルすると、次のようになります。

これを修正する方法または回避する方法を知っている人はいますか?