Java Reference
In-Depth Information
1 /**
2 * Internal method that is the basic operation to maintain order.
3 * Links first and second together to satisfy heap order.
4 * @param first root of tree 1, which may not be null.
5 * first.nextSibling MUST be null on entry.
6 * @param second root of tree 2, which may be null.
7 * @return result of the tree merge.
8 */
9 private PairNode<AnyType> compareAndLink( PairNode<AnyType> first,
10 PairNode<AnyType> second )
11 {
12 if( second == null )
13 return first;
14
15 if( second.element.compareTo( first.element ) < 0 )
16 {
17 // Attach first as leftmost child of second
18 second.prev = first.prev;
19 first.prev = second;
20 first.nextSibling = second.leftChild;
21 if( first.nextSibling != null )
22 first.nextSibling.prev = first;
23 second.leftChild = first;
24 return second;
25 }
26 else
27 {
28 // Attach second as leftmost child of first
29 second.prev = first;
30 first.nextSibling = second.nextSibling;
31 if( first.nextSibling != null )
32 first.nextSibling.prev = first;
33 second.nextSibling = first.leftChild;
34 if( second.nextSibling != null )
35 second.nextSibling.prev = second;
36 first.leftChild = second;
37 return first;
38 }
39 }
figure 23.14
The compareAndLink routine
that represents its position in the priority queue (and is null if the Vertex is
not in the priority queue). Initially, all the positions are null (which is done
in clearAll ). Whenever a vertex is inserted in the pairing heap, we adjust its
pos data member—at lines 13 and 35. The algorithm itself is simplified.
Now we merely call deleteMin so long as the pairing heap is not empty,
Search WWH ::




Custom Search