fr.inria.opengve.tools.dataStructures
Class FibonacciHeap<E,V extends java.lang.Comparable<V>>

java.lang.Object
  fr.inria.opengve.tools.dataStructures.FibonacciHeap<E,V>

Type Parameters:

E - The type of element in the heap.

V - The type of value associated with element in the heap.

All Implemented Interfaces:

PriorityQueue<E,V>

public class FibonacciHeap<E,V extends java.lang.Comparable<V>>
extends java.lang.Object
implements PriorityQueue<E,V>

The Fibonacci Heap.

Author:

Jean-Francois Lalande (Jean-Francois.Lalande@sophia.inria.fr), fabrice.peix@sophia.inria.fr

Constructor Summary

FibonacciHeap()
Construct the Fibonacci heap.

Method Summary

void	clear() Make the priority queue logically empty.
boolean	contains(E element) Say if the priority queue contains a given elemeent.
E	deleteMin() Remove the smallest item from the priority queue.
void	FibHeapDecreaseKey(E element, V value) Update the value of an element of the heap.
E	findMin() Find the smallest item in the priority queue.
V	getValueOf(E element) Give the value of a given element.
void	insert(E x, V value) Insert into the priority queue.
boolean	isEmpty() Test if the priority queue is logically empty.

Methods inherited from class java.lang.Object

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

Constructor Detail

FibonacciHeap

public FibonacciHeap()

Construct the Fibonacci heap.

Method Detail

isEmpty

public boolean isEmpty()

Description copied from interface: PriorityQueue

Test if the priority queue is logically empty.

Specified by:

isEmpty in interface PriorityQueue<E,V extends java.lang.Comparable<V>>

Returns:

true if empty, false otherwise.

clear

public void clear()

Description copied from interface: PriorityQueue

Make the priority queue logically empty.

Specified by:

clear in interface PriorityQueue<E,V extends java.lang.Comparable<V>>

findMin

public E findMin()
          throws java.util.NoSuchElementException

Description copied from interface: PriorityQueue

Find the smallest item in the priority queue.

Specified by:

findMin in interface PriorityQueue<E,V extends java.lang.Comparable<V>>

Returns:

the smallest item.

Throws:

java.util.NoSuchElementException - if the priority queue is empty.

deleteMin

public E deleteMin()

Remove the smallest item from the priority queue.

Specified by:

deleteMin in interface PriorityQueue<E,V extends java.lang.Comparable<V>>

Returns:

the smallest item.

Throws:

Underflow - if the priority queue is empty.

java.util.NoSuchElementException - If the heap is empty.

FibHeapDecreaseKey

public void FibHeapDecreaseKey(E element,
                               V value)
                        throws java.lang.IllegalArgumentException

Update the value of an element of the heap. If the element is not in the heap this methods just add it.

Parameters:

element - The element that we update.

value - The new value for this element.

Throws:

java.lang.IllegalArgumentException - If the new value is greater that old one.

insert

public void insert(E x,
                   V value)

Description copied from interface: PriorityQueue

Insert into the priority queue. Duplicate are allowed.

Specified by:

insert in interface PriorityQueue<E,V extends java.lang.Comparable<V>>

Parameters:

x - The object to insert.

value - The value of the object.

contains

public boolean contains(E element)

Description copied from interface: PriorityQueue

Say if the priority queue contains a given elemeent.

Specified by:

contains in interface PriorityQueue<E,V extends java.lang.Comparable<V>>

Parameters:

element - The element.

Returns:

true if the element belong to the priority queue and false otherwise.

getValueOf

public V getValueOf(E element)

Description copied from interface: PriorityQueue

Give the value of a given element.

Specified by:

getValueOf in interface PriorityQueue<E,V extends java.lang.Comparable<V>>

Parameters:

element - The element.

Returns:

The value of element.