gishur.core
Class FibonacciHeap

java.lang.Object
  |
  +--gishur.core.FibonacciHeap
All Implemented Interfaces:
PriorityQueue

public class FibonacciHeap
extends java.lang.Object
implements PriorityQueue

A FibonacciHeap is a PriorityQueue. The elements of the FibonacciHeap are FibonacciNodes.
The key of a FibonacciNode defines the priority and can be any object (e.g. a Number), which will be compared to the keys of the other FibonacciNodes by a Comparitor selected by setComparitor(gishur.core.Comparitor).
The elements are queued in increasing order, thus a lower key indicates a higher priority.
The value of a FibonacciNode contains the actual object, which was inserted into the FibonacciHeap.

Version:
1.0
Author:
Simon Weidmann

Constructor Summary
FibonacciHeap()
          Creates an empty FibonacciHeap and sets the StdComparitor as Comparitor for comparing FibonacciNodes
FibonacciHeap(Comparitor c)
          Creates an empty FibonacciHeap and sets c as Comparitor for comparing FibonacciNodes
 
Method Summary
 void clear()
          Removes all the elements from the FibonacciHeap.
 Comparitor comparitor()
          Returns the Comparitor used to compare the elements of this FibonacciHeap.
 void decreaseKey(java.lang.Object k, KeyValueHolder p)
          Decreases the key of p to k, only if k is Comparitor.SMALLER than the current key of p.
 void delete(KeyValueHolder p)
          Deletes the element p from the FibonacciHeap
 boolean empty()
          Tests, if the FibonacciHeap is empty.
 KeyValueHolder extractMin()
          Deletes the the entry with the minimum key and returns it.
 FibonacciNode insert(FibonacciNode p)
          Inserts the FibonacciNode p into the FibonacciHeap.
 KeyValueHolder insert(KeyValueHolder p)
          Creates a new FibonacciNode with a priority equal to p.{
 void meld(PriorityQueue Q)
          Melds this FibonacciHeap with the FibonacciHeap Q, which will be empty after this operation.
 KeyValueHolder min()
          Returns the FibonacciNode with the minimum key
 void setComparitor(Comparitor c)
          Sets the Comparitor, used to compare the priorities of the heap elements
 java.lang.String toString()
          Overrides java.lang.Object.toString().
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

FibonacciHeap

public FibonacciHeap()
Creates an empty FibonacciHeap and sets the StdComparitor as Comparitor for comparing FibonacciNodes

FibonacciHeap

public FibonacciHeap(Comparitor c)
Creates an empty FibonacciHeap and sets c as Comparitor for comparing FibonacciNodes
Parameters:
c, - @link Comparitor} for comparing FibonacciNodes
Method Detail

clear

public void clear()
Removes all the elements from the FibonacciHeap.

setComparitor

public void setComparitor(Comparitor c)
Sets the Comparitor, used to compare the priorities of the heap elements
Specified by:
setComparitor in interface PriorityQueue
Parameters:
Comparitor - for comparing the priorities of the heap elements

comparitor

public Comparitor comparitor()
Returns the Comparitor used to compare the elements of this FibonacciHeap.
Specified by:
comparitor in interface PriorityQueue
Returns:
the Comparitor used to compare the elements of this FibonacciHeap.

empty

public boolean empty()
Tests, if the FibonacciHeap is empty.
Specified by:
empty in interface PriorityQueue
Returns:
true, if the FibonacciHeap is empty, false otherwise.

meld

public void meld(PriorityQueue Q)
Melds this FibonacciHeap with the FibonacciHeap Q, which will be empty after this operation. Q must be a FibonacciHeap, otherwise this method will not work.
Specified by:
meld in interface PriorityQueue
Parameters:
Q - FibonacciHeap, which should be melded with this

insert

public KeyValueHolder insert(KeyValueHolder p)
Creates a new FibonacciNode with a priority equal to p.key() and a value equal to p.value() and inserts it into the FibonacciHeap.
Specified by:
insert in interface PriorityQueue
Parameters:
p - KeyValueHolder containing the Object to be inserted (as value) and its priority (as key)
Returns:
the actual FibonacciNode, inserted into the FibonacciHeap
See Also:
KeyValueHolder

insert

public FibonacciNode insert(FibonacciNode p)
Inserts the FibonacciNode p into the FibonacciHeap.
Parameters:
p - FibonacciNode to be inserted
Returns:
the FibonacciNode, inserted into the FibonacciHeap

extractMin

public KeyValueHolder extractMin()
Deletes the the entry with the minimum key and returns it. If this FibonacciHeap is empty, null will be returned.
Specified by:
extractMin in interface PriorityQueue
Returns:
FibonacciNode with the minimum key

decreaseKey

public void decreaseKey(java.lang.Object k,
                        KeyValueHolder p)
Decreases the key of p to k, only if k is Comparitor.SMALLER than the current key of p. This operation increases the priority of p. P must be a FibonacciNode, otherwise this method will not work.
Specified by:
decreaseKey in interface PriorityQueue
Parameters:
k - new key of p
p - element the key of which will be decreased

delete

public void delete(KeyValueHolder p)
Deletes the element p from the FibonacciHeap
Specified by:
delete in interface PriorityQueue
Parameters:
p - element to be deleted

min

public KeyValueHolder min()
Returns the FibonacciNode with the minimum key
Specified by:
min in interface PriorityQueue
Returns:
the FibonacciNode with the minimum key

toString

public java.lang.String toString()
Overrides java.lang.Object.toString().
Overrides:
toString in class java.lang.Object
See Also:
Object.toString()