Java Reference
In-Depth Information
Figure 23.4 shows an abstract pairing heap. The actual implementa-
tion uses a left child/right sibling representation (see Chapter 18). The
decreaseKey
method, as we discuss shortly, requires that each node contain an
additional link. A node that is a leftmost child contains a link to its parent;
otherwise, the node is a right sibling and contains a link to its left sibling. This
representation is shown in Figure 23.5, where the darkened line indicates that
two links (one in each direction) connect pairs of nodes.
The pairing heap is
stored by using a
left child/right sib-
ling representation.
A third link is used
for
decreaseKey
.
23.2.1
pairing heap operations
In principle, the basic pairing heap operations are simple, which is why the
pairing heap performs well in practice. To merge two pairing heaps, we
make the heap with the larger root the new first child of the heap with the
smaller root. Insertion is a special case of merging. To perform a
decreaseKey
operation, we lower the value of the requested node. Because we are not
maintaining parent links for all nodes, we do not know if this action violates
the heap order. Thus we detach the adjusted node from its parent and com-
plete
decreaseKey
by merging the two pairing heaps that result. Figure 23.5
shows that detaching a node from its parent means removing it from what is
essentially a linked list of children. So far we are in great shape: Every oper-
ation described takes constant time. However, we are not so lucky with the
deleteMin
operation.
Merging is simple:
Attach the larger
root tree as a left
child of the smaller
root tree. Insertion
and decreasing are
also simple.
figure 23.4
Abstract
representation of a
sample pairing heap
2
6
3
4
5
9
7
10
13
8
11
15
14
12
17
19
16
18
figure 23.5
Actual representation
of the pairing heap
shown in Figure 23.4;
the dark lines
represent a pair of
links that connect
nodes in both
directions
2
6
3
4
5
9
7
10
13
8
11
15
14
12
17
19
16
18
Search WWH ::
Custom Search