基于Java的Dijkstra Fibonacci堆

Question

我想在Dijkstra算法上实现Fibonacci堆。我对Fibonacci堆使用了这段代码。http://keithschwarz.com/interesting/code/?dir=fibonacci-heap问题是如何调用方法: decreaseKey？它总是给我提示(入口，双)。但是怎么写一个条目呢？下面是一个简单的例子，如何填写问号？

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个方法返回堆的Entrys：

• 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);