All Packages Class Hierarchy This Package Previous Next Index
Class DataStructures.PairHeap
java.lang.Object

+DataStructures.PairHeap
 public class PairHeap
 extends Object
 implements PriorityQueue
Implements a pairing heap.
Supports a decreaseKey operation, but requires use
of addItem instead of insert.
Heap order is always maintained; no lazy operations allowed.
Note that all "matching" is based on the compares method.
 See Also:
 PairNode

PairHeap()
 Construct the pairing heap.

addItem(Comparable)
 Insert into the priority queue, and return a PairNode
that can be used by decreaseKey.

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.

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 void insert(Comparable x)
 Insert into the priority queue.
Duplicates are allowed.
 Parameters:
 x  the item to insert.
addItem
public PairNode addItem(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() throws Underflow
 Find the smallest item in the priority queue.
 Returns:
 the smallest item.
 Throws:
Underflow
 if the priority queue is empty.
deleteMin
public Comparable deleteMin() throws Underflow
 Remove the smallest item from the priority queue.
 Throws:
Underflow
 if the priority queue is empty.
decreaseKey
public void decreaseKey(PairNode p,
Comparable newVal) throws IllegalValue
 Change the value of the item stored in the pairing heap.
 Parameters:
 p  any node returned by addItem.
 newVal  the new value, which must be smaller
than the currently stored value.
 Throws:
IllegalValue
 if newVal is larger
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