フィボナッチヒープfor Dijkstra via Java

Question

Dijkstraアルゴリズムでフィボナッチヒープを実装したい。私はフィボナッチヒープのためにこのコードを使用します。 http://keithschwarz.com/interesting/code/?dir=fibonacci-heap 問題を呼び出す方法は、reduceKeyですか？それは常に私に（エントリー、ダブル）というヒントを与えます。しかし、エントリを書く方法は？以下は、疑問符を記入する簡単な例です。

FibonacciHeap<Integer> aa = new FibonacciHeap<>(); 
aa.enqueue(10, 1.01); 
aa.enqueue(10, .2); 
aa.enqueue(12, 3.2); 
aa.enqueue(13, 3.4); 
aa.decreaseKey(??????, newPriority); 

Answer 1

decreaseKey()は、最初の引数は、型FibonacciHeap.Entryであることを期待します。クラスの3つの方法は、ヒープのEntry S返す：3つの方法

• public Entry<T> enqueue(T value, double priority);
• public Entry<T> min();
• public Entry<T> dequeueMin();

それぞれ異なる要素を返すが、それらにヒープを変更します独自のやり方。ユースケースによっては、Entryを変数に格納してdecreaseKey()に渡すことができます。それをエンキューしながら

そのような場合は、Entryを記憶することになります。あなたはヒープにenqueue()何か、それは返すたびにそのEntry対応します。そのマニュアルから：

/** 
* Inserts the specified element into the Fibonacci heap with the specified 
* priority. 
* ... 
* @return An Entry representing that element in the tree. 
*/ 
public Entry<T> enqueue(T value, double priority); 

あなたはそれを保存することができ、かつdecreaseKey()に渡します。

FibonacciHeap<Integer> aa = new FibonacciHeap<>(); 
FibonacciHeap.Entry entry = aa.enqueue(10, 1.01); 
// ... 
aa.decreaseKey(entry, newPriority);