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

The decreaseKey method is implemented in Figure 23.12. If the new value
is larger than the original, we might destroy the heap order. We have no way
of knowing that without examining all the children. Because many children
may exist, doing so would be inefficient. Thus we assume that it is always an
error to attempt to increase the key by using the decreaseKey . (In Exercise 23.9
you are asked to describe an algorithm for increaseKey .) After performing this
test, we lower the value in the node. If the node is the root, we are done. Oth-
erwise, we splice the node out of the list of children that it is in, using the code
in lines 21 to 28. After doing that, we merely merge the resulting tree with the
root.
The two remaining routines are compareAndLink , which combines two
trees, and combineSiblings , which combines all the siblings, when given the
first sibling. Figure 23.13 shows how two subheaps are combined. The proce-
dure is generalized to allow the second subheap to have siblings (which is
needed for the second pass in the two-pass merge). As mentioned earlier in

1 /**
2 * Change the value of the item stored in the pairing heap.
3 * @param pos any Position returned by insert.
4 * @param newVal the new value, which must be smaller
5 * than the currently stored value.
6 * @throws IllegalArgumentException if pos is null.
7 * @throws IllegalValueException if new value is larger than old.
8 */
9 public void decreaseKey( Position<AnyType> pos, AnyType newVal )
10 {
11 if( pos == null )
12 throw new IllegalArgumentException( );
13
14 PairNode<AnyType> p = (PairNode<AnyType>) pos;
15
16 if( p.element == null || p.element.compareTo( newVal ) < 0 )
17 throw new IllegalValueException( );
18 p.element = newVal;
19 if( p != root )
20 {
21 if( p.nextSibling != null )
22 p.nextSibling.prev = p.prev;
23 if( p.prev.leftChild == p )
24 p.prev.leftChild = p.nextSibling;
25 else
26 p.prev.nextSibling = p.nextSibling;
27
28 p.nextSibling = null;
29 root = compareAndLink( root, p );
30 }
31 }

figure 23.12
The decreaseKey
method for the
PairingHeap class