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