Tas de Fibonacci pour Dijkstra via Java

Question

Je veux implémenter Fibonacci Heap sur Dijkstra Algorithm. J'utilise ce code pour le tas de Fibonacci. http://keithschwarz.com/interesting/code/?dir=fibonacci-heap Le problème est de savoir comment appeler la méthode: baisseKey? Cela me donne toujours l'indice que (entrée, double). Mais comment écrire une entrée? Ce qui suit est un exemple simple, comment remplir le point d'interrogation?

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() attend le premier argument est de type FibonacciHeap.Entry. 3 méthodes de la classe renvoient les Entry s du tas:

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

Chacune des 3 méthodes retourner un élément différent, et de modifier le tas dans leur sa propre façon. Selon votre cas d'utilisation, vous pouvez stocker ces Entry s dans une variable et les transmettre à decreaseKey().

Un de ces cas consisterait à stocker le Entry lors de la mise en file d'attente. Chaque fois que vous enqueue() quelque chose au tas, il renvoie le Entry correspondant. De la documentation:

/** 
* 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); 

Vous pouvez stocker et transmettre à decreaseKey().

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