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

figure 23.10
The insert routine for
the PairingHeap class

1 /**
2 * Insert into the priority queue, and return a Position
3 * that can be used by decreaseKey.
4 * Duplicates are allowed.
5 * @param x the item to insert.
6 * @return the node containing the newly inserted item.
7 */
8 public Position<AnyType> insert( AnyType x )
9 {
10 PairNode<AnyType> newNode = new PairNode<AnyType>( x );
11
12 if( root == null )
13 root = newNode;
14 else
15 root = compareAndLink( root, newNode );
16
17 theSize++;
18 return newNode;
19 }

Figure 23.11 implements the deleteMin routine. If the pairing heap is
empty, we have an error. After saving the value found in the root (at line 11)
and clearing the value at line 12, we make a call to combineSiblings at line 16
to merge the root's subtrees and set the result to the new root. If there are no
subtrees, we merely set root to null at line 14.

The deleteMin
operation is imple-
mented as a call to
combineSibling s.

1 /**
2 * Remove the smallest item from the priority queue.
3 * @return the smallest item.
4 * @throws UnderflowException if pairing heap is empty.
5 */
6 public AnyType deleteMin( )
7 {
8 if( isEmpty( ) )
9 throw new UnderflowException( );
10
11 AnyType x = findMin( );
12 root.element = null; // So decreaseKey can detect stale Position
13 if( root.leftChild == null )
14 root = null;
15 else
16 root = combineSiblings( root.leftChild );
17
18 theSize--;
19 return x;
20 }

figure 23.11
The deleteMin method for the PairingHeap class