Merging priority queues - Data Structures and Problem Solving Using Java - page 881

1 /**
2 * Private static class for use with PairingHeap.
3 */
4 private static class PairNode<AnyType> implements Position<AnyType>
5 {
6 /**
7 * Construct the PairNode.
8 * @param theElement the value stored in the node.
9 */
10 public PairNode( AnyType theElement )
11 {
12 element = theElement;
13 leftChild = null;
14 nextSibling = null;
15 prev = null;
16 }
17
18 /**
19 * Returns the value stored at this position.
20 */
21 public AnyType getValue( )
22 {
23 return element;
24 }
25
26 public AnyType element;
27 public PairNode<AnyType> leftChild;
28 public PairNode<AnyType> nextSibling;
29 public PairNode<AnyType> prev;
30 }

figure 23.8
The PairNode nested class

1 /**
2 * Find the smallest item in the priority queue.
3 * @return the smallest item.
4 * @throws UnderflowException if pairing heap is empty.
5 */
6 public AnyType findMin( )
7 {
8 if( isEmpty( ) )
9 throw new UnderflowException( );
10 return root.element;
11 }

figure 23.9
The findMin method
for the PairingHeap
class