Dijkstra 的斐波那契堆来自 Java

Question

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

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 类型。 class return 堆的 Entry 中的 3 个方法：

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

3 种方法中的每一种 return 一个不同的元素，并以自己的方式修改堆。根据您的用例，您可以将这些 Entry 存储在一个变量中并将其传递给 decreaseKey().

一个这样的情况是在排队时存储 Entry。每当你 enqueue() 一些东西到堆中时，它 return 就是它对应的 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);

Dijkstra 的斐波那契堆来自 Java

Fibonacci Heap for Dijkstra via Java

java

dijkstra