mascoptLib.util.fibHeap
Class FibonacciHeap

java.lang.Object
  |
  +--mascoptLib.util.fibHeap.FibonacciHeap

All Implemented Interfaces:

PriorityQueue

public class FibonacciHeap

extends Object

implements PriorityQueue

The Fibonacci Heap.

Author:

Jean-Francois Lalande (Jean-Francois.Lalande@sophia.inria.fr)

Constructor Summary

FibonacciHeap(mascoptLib.abstractGraph.AbstractGraph g)
Construct the Fibonacci heap.

Method Summary

Object	deleteMin() Remove the smallest item from the priority queue.
void	FibHeapDecreaseKey(mascoptLib.util.fibHeap.FibHeapNode x, Object k)
void	FibHeapUnion(mascoptLib.util.fibHeap.FibHeapNode fhn, int n)
Object	findMin() Find the smallest item in the priority queue.
mascoptLib.util.fibHeap.FibHeapNode	getNode(int index)
int	insert(Object x) Insert into the priority queue, maintaining heap order.
boolean	isEmpty() Test if the priority queue is logically empty.
void	makeEmpty() Make the priority queue logically empty.
void	toss(Object x) Insert into the priority queue, without maintaining heap order.
void	validate() Validate the Heap

Methods inherited from class java.lang.Object

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

Constructor Detail

FibonacciHeap

public FibonacciHeap(mascoptLib.abstractGraph.AbstractGraph g)

Construct the Fibonacci heap.

Method Detail

insert

public int insert(Object x)

Insert into the priority queue, maintaining heap order. Duplicates are allowed.

Specified by:

insert in interface PriorityQueue

Parameters:

x - the item to insert.

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Specified by:

isEmpty in interface PriorityQueue

Returns:

true if empty, false otherwise.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

Specified by:

makeEmpty in interface PriorityQueue

findMin

public Object findMin()
               throws Underflow

Find the smallest item in the priority queue.

Specified by:

findMin in interface PriorityQueue

Returns:

the smallest item.

Throws:

Underflow - if the priority queue is empty.

FibHeapUnion

public void FibHeapUnion(mascoptLib.util.fibHeap.FibHeapNode fhn,
                         int n)

deleteMin

public Object deleteMin()
                 throws Underflow

Remove the smallest item from the priority queue.

Specified by:

deleteMin in interface PriorityQueue

Throws:

Underflow - if the priority queue is empty.

toss

public void toss(Object x)

Insert into the priority queue, without maintaining heap order. Duplicates are allowed.

Specified by:

toss in interface PriorityQueue

Parameters:

x - the item to insert.

validate

public void validate()

Validate the Heap

Specified by:

validate in interface PriorityQueue

FibHeapDecreaseKey

public void FibHeapDecreaseKey(mascoptLib.util.fibHeap.FibHeapNode x,
                               Object k)
                        throws Underflow

Underflow

getNode

public mascoptLib.util.fibHeap.FibHeapNode getNode(int index)