|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Objectweiss.nonstandard.PairingHeap<AnyType>
public class PairingHeap<AnyType extends java.lang.Comparable<? super AnyType>>
Implements a pairing heap. Supports a decreaseKey operation. Note that all "matching" is based on the compareTo method.
PriorityQueue.Position| Nested Class Summary | |
|---|---|
static interface |
PairingHeap.Position<AnyType>
The Position interface represents a type that can be used for the decreaseKey operation. |
| Constructor Summary | |
|---|---|
PairingHeap()
Construct the pairing heap. |
|
| Method Summary | |
|---|---|
void |
decreaseKey(PairingHeap.Position<AnyType> pos,
AnyType newVal)
Change the value of the item stored in the pairing heap. |
AnyType |
deleteMin()
Remove the smallest item from the priority queue. |
AnyType |
findMin()
Find the smallest item in the priority queue. |
PairingHeap.Position<AnyType> |
insert(AnyType 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 PairingHeap.Position<AnyType> insert(AnyType x)
x - the item to insert.
public AnyType findMin()
UnderflowException - if pairing heap is empty.public AnyType deleteMin()
UnderflowException - if pairing heap is empty.
public void decreaseKey(PairingHeap.Position<AnyType> pos,
AnyType newVal)
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()
public int size()
public void makeEmpty()
public static void main(java.lang.String[] args)
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||