|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--gishur.core.FibonacciHeap
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.
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 |
public FibonacciHeap()
StdComparitor
as Comparitor
for comparing FibonacciNodespublic FibonacciHeap(Comparitor c)
Comparitor
for comparing
FibonacciNodesc,
- @link Comparitor} for comparing FibonacciNodesMethod Detail |
public void clear()
public void setComparitor(Comparitor c)
Comparitor
, used to compare the priorities of the heap elementssetComparitor
in interface PriorityQueue
Comparitor
- for comparing the priorities of the heap elementspublic Comparitor comparitor()
Comparitor
used to compare the elements of this FibonacciHeap.comparitor
in interface PriorityQueue
Comparitor
used to compare the elements of this FibonacciHeap.public boolean empty()
empty
in interface PriorityQueue
true
, if the FibonacciHeap is empty, false
otherwise.public void meld(PriorityQueue Q)
this
FibonacciHeap with the FibonacciHeap Q, which will be
empty after this operation.
Q must be a FibonacciHeap, otherwise this method will not work.meld
in interface PriorityQueue
Q
- FibonacciHeap, which should be melded with this
public KeyValueHolder insert(KeyValueHolder p)
key()
and a value equal to p.value()
and inserts it into
the FibonacciHeap.insert
in interface PriorityQueue
p
- KeyValueHolder containing the Object to be inserted (as value) and its priority (as key)KeyValueHolder
public FibonacciNode insert(FibonacciNode p)
p
- FibonacciNode to be insertedpublic KeyValueHolder extractMin()
this
FibonacciHeap is empty, null
will be returned.extractMin
in interface PriorityQueue
public void decreaseKey(java.lang.Object k, KeyValueHolder p)
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.decreaseKey
in interface PriorityQueue
k
- new key of pp
- element the key of which will be decreasedpublic void delete(KeyValueHolder p)
delete
in interface PriorityQueue
p
- element to be deletedpublic KeyValueHolder min()
min
in interface PriorityQueue
public java.lang.String toString()
java.lang.Object.toString()
.toString
in class java.lang.Object
Object.toString()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |