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

1 // The tree array for combineSiblings
2 private PairNode [ ] treeArray = new PairNode[ 5 ];
3
4 /**
5 * Internal method that implements two-pass merging.
6 * @param firstSibling the root of the conglomerate;
7 * assumed not null.
8 */
9 private PairNode<AnyType> combineSiblings( PairNode<AnyType> firstSibling )
10 {
11 if( firstSibling.nextSibling == null )
12 return firstSibling;
13
14 // Store the subtrees in an array
15 int numSiblings = 0;
16 for( ; firstSibling != null; numSiblings++ )
17 {
18 treeArray = doubleIfFull( treeArray, numSiblings );
19 treeArray[ numSiblings ] = firstSibling;
20 firstSibling.prev.nextSibling = null; // break links
21 firstSibling = firstSibling.nextSibling;
22 }
23 treeArray = doubleIfFull( treeArray, numSiblings );
24 treeArray[ numSiblings ] = null;
25
26 // Combine subtrees two at a time, going left to right
27 int i = 0;
28 for( ; i + 1 < numSiblings; i += 2 )
29 treeArray[ i ] = compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );
30
31 int j = i - 2;
32
33 // j has the result of last compareAndLink.
34 // If an odd number of trees, get the last one.
35 if( j == numSiblings - 3 )
36 treeArray[ j ] = compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );
37
38 // Now go right to left, merging last tree with
39 // next to last. The result becomes the new last.
40 for( ; j >= 2; j -= 2 )
41 treeArray[ j - 2 ] = compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );
42
43 return (PairNode<AnyType>) treeArray[ 0 ];
44 }
figure 23.15
The heart of the pairing heap algorithm: implementing a two-pass merge to combine all the siblings,
given the first sibling