All Packages Class Hierarchy This Package Previous Next Index
Class DataStructures.PairHeap
java.lang.Object
|
+----DataStructures.PairHeap
- public class PairHeap
- extends Object
Implements a pairing heap.
Supports a decreaseKey operation.
Note that all "matching" is based on the compareTo method.
- See Also:
- PairNode
PairHeap()
- Construct the pairing heap.
decreaseKey(PairNode, Comparable)
- Change the value of the item stored in the pairing heap.
deleteMin()
- Remove the smallest item from the priority queue.
findMin()
- Find the smallest item in the priority queue.
insert(Comparable)
- Insert into the priority queue, and return a PairNode
that can be used by decreaseKey.
isEmpty()
- Test if the priority queue is logically empty.
main(String[])
-
makeEmpty()
- Make the priority queue logically empty.
PairHeap
public PairHeap()
- Construct the pairing heap.
insert
public PairNode insert(Comparable x)
- Insert into the priority queue, and return a PairNode
that can be used by decreaseKey.
Duplicates are allowed.
- Parameters:
- x - the item to insert.
- Returns:
- the node containing the newly inserted item.
findMin
public Comparable findMin()
- Find the smallest item in the priority queue.
- Returns:
- the smallest item, or null if empty.
deleteMin
public Comparable deleteMin()
- Remove the smallest item from the priority queue.
- Returns:
- the smallest item, or null if empty.
decreaseKey
public void decreaseKey(PairNode p,
Comparable newVal)
- Change the value of the item stored in the pairing heap.
Does nothing if newVal is larger than the currently stored value.
- Parameters:
- p - any node returned by addItem.
- newVal - the new value, which must be smaller
than the currently stored value.
isEmpty
public boolean isEmpty()
- Test if the priority queue is logically empty.
- Returns:
- true if empty, false otherwise.
makeEmpty
public void makeEmpty()
- Make the priority queue logically empty.
main
public static void main(String[] args)
All Packages Class Hierarchy This Package Previous Next Index