|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--weiss.nonstandard.PairingHeap
Implements a pairing heap. Supports a decreaseKey operation. Note that all "matching" is based on the compareTo method.
PriorityQueue.Position
Inner classes inherited from class weiss.nonstandard.PriorityQueue |
PriorityQueue.Position |
Constructor Summary | |
PairingHeap()
Construct the pairing heap. |
Method Summary | |
void |
decreaseKey(PriorityQueue.Position pos,
java.lang.Comparable newVal)
Change the value of the item stored in the pairing heap. |
java.lang.Comparable |
deleteMin()
Remove the smallest item from the priority queue. |
java.lang.Comparable |
findMin()
Find the smallest item in the priority queue. |
PriorityQueue.Position |
insert(java.lang.Comparable x)
Insert into the priority queue, and return a Position that can be used by decreaseKey. |
boolean |
isEmpty()
Test if the priority queue is logically empty. |
static void |
main(java.lang.String[] args)
|
void |
makeEmpty()
Make the priority queue logically empty. |
int |
size()
Returns number of items stored in the priority queue. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
public PairingHeap()
Method Detail |
public PriorityQueue.Position insert(java.lang.Comparable x)
insert
in interface PriorityQueue
x
- the item to insert.public java.lang.Comparable findMin()
findMin
in interface PriorityQueue
UnderflowException
- if pairing heap is empty.public java.lang.Comparable deleteMin()
deleteMin
in interface PriorityQueue
UnderflowException
- if pairing heap is empty.public void decreaseKey(PriorityQueue.Position pos, java.lang.Comparable newVal)
decreaseKey
in interface PriorityQueue
pos
- any Position returned by insert.newVal
- the new value, which must be smaller
than the currently stored value.java.lang.IllegalArgumentException
- if pos is null.IllegalValueException
- if new value is larger than old.public boolean isEmpty()
isEmpty
in interface PriorityQueue
public int size()
size
in interface PriorityQueue
public void makeEmpty()
makeEmpty
in interface PriorityQueue
public static void main(java.lang.String[] args)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |