com.kuka.graph.util
Class FibonacciHeap<K extends Comparable<K>,T>

java.lang.Object
  com.kuka.graph.util.FibonacciHeap<K,T>

Type Parameters:

K - the key type

T - the value type

public final class FibonacciHeap<K extends Comparable<K>,T>
extends Object

This Fibonacci heap is a special implementation of a priority queue tailored for graph search algorithms. Its interface is different to a standard Java PriorityQueue to facilitate an efficient "decreaseKey" operation, which reduces the priority of a value that is already in the queue. Thus, Handles are used to reference directly values already in the heap.

Nested Class Summary

static class

FibonacciHeap.Handle<C,V> Handle to elements in the heap for efficient access.

Constructor Summary

FibonacciHeap()

Method Summary

void	decreaseKey(FibonacciHeap.Handle<K,T> h, K lowerKey) Decreases the priority of an element that is already in the heap.
FibonacciHeap.Handle<K,T>	insert(K key, T item) Inserts an element into the heap.
boolean	isEmpty() Returns true if this heap contains no elements.
T	removeMin() Returns and removes the element with lowest priority.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

FibonacciHeap

public FibonacciHeap()

Method Detail

isEmpty

public boolean isEmpty()

Returns true if this heap contains no elements.

Returns:

true if this heap contains no elements

insert

public FibonacciHeap.Handle<K,T> insert(K key,
                                        T item)

Inserts an element into the heap.

Parameters:

key - the priority of the element

item - the element to be inserted

Returns:

a handle for modifying the priority of the element in the heap

removeMin

public T removeMin()

Returns and removes the element with lowest priority.

Returns:

the element with the lowest priority in the heap

decreaseKey

public void decreaseKey(FibonacciHeap.Handle<K,T> h,
                        K lowerKey)

Decreases the priority of an element that is already in the heap.

Parameters:

h - the handle of an element already in the heap

lowerKey - the new priority of the element, which must be lower than the old one

toString

public String toString()

Overrides:

toString in class Object