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

To perform a deleteMin , we must remove the root of the tree, creating a
collection of heaps. If there are c children of the root, combining these heaps
into one heap requires c - 1 merges. Hence, if there are lots of children of the
root, the deleteMin operation costs lots of time. If the insertion sequence is 1,
2, ..., N, then 1 is at the root and all the other items are in nodes that are chil-
dren of the root. Consequently, deleteMin is O ( N ) time. The best that we can
hope to do is to arrange the merges so that we do not have repeatedly expen-
sive deleteMin operations.

The deleteMin
operation is expen-
sive because the
new root could be
any of the c
children of the old
root. We need
c - 1 merges.

The order in which pairing heap subtrees are merged is important. The
simplest and most practical of the many variants of doing so that have been
proposed is two-pass merging, in which a first scan merges pairs of children
from left to right 2 and then a second scan, right to left, is performed to com-
plete the merging. After the first scan, we have half as many trees to merge. In
the second scan, at each step, we merge the rightmost tree that remains from
the first scan with the current merged result. For example, if we have children
c 1 through c 8 , the first scan performs the merges c 1 and c 2 , c 3 and c 4 , c 5 and
c 6 , and c 7 and c 8 . The result is d 1 , d 2 , d 3 , and d 4 . We perform the second pass
by merging d 3 and d 4 ; d 2 is then merged with that result, and d 1 is then
merged with the result of that merge, completing the deleteMin operation.
Figure 23.6 shows the result of using deleteMin on the pairing heap shown in
Figure 23.5.

The order in which
pairing heap sub-
trees are merged is
important. The sim-
plest algorithm is
two-pass merging .

Other merging strategies are possible. For instance, we can place each
subtree (corresponding to a child) on a queue, repeatedly dequeue two trees,
and then enqueue the result of merging them. After c - 1 merges, only one
tree remains on the queue, which is the result of the deleteMin . However,
using a stack instead of a queue is a disaster because the root of the resulting
tree may possibly have c - 1 children. If that occurs in a sequence, the
deleteMin operation will have linear, rather than logarithmic, amortized cost
per operation. In Exercise 23.8 you are asked to construct such a sequence.

Several alterna-
tives have been
proposed. Most are
indistinguishable,
but using a single
left-to-right pass is
a bad idea.

23.2.2 implementation of the pairing heap

The PairingHeap class skeleton is shown in Figure 23.7. The nested class
PairNode implements the nested Position interface that is declared at lines
16 and 17.
In the pairing heap, insert returns a Position which is the newly created
PairNode .
The basic node of a pairing heap, PairNode , is shown in Figure 23.8 and
consists of an item and three links. Two of these links are the left child and the

The prev data
member links to
either a left sibling
or a parent.

2. Care must be exercised if there is an odd number of children. When that happens, we merge
the last child with the result of the rightmost merge to complete the first scan.