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

figure 23.3
Change in the heavy
or light status of
nodes after a merge

L H L

2 4 2

+

L

L L

3 8 9 5 4 3

L

6 7 5 9 6

L

8 7

In Figure 23.3, prior to the merge, nodes 3 and 4 are heavy. After the
merge, only node 3 is heavy. Three facts are easily shown. First, as a result of
a merge, only nodes on the right path can have their heavy or light status
changed because no other nodes have their subtrees altered. Second, a leaf is
light. Third, the number of light nodes on the right path of an N node tree is at most
⎣ log N ⎦ + 1. The reason is that the right child of a light node is less than half the
size of the light node itself, and the halving principle applies. The additional
+1 is a result of the leaf's being light. With these preliminaries, we can now
state and prove Theorems 23.1 and 23.2.

The potential func-
tion is the number
of heavy nodes.
Only nodes on the
merged path have
their heavy or light
status changed.
The number of light
nodes on a right
path is logarithmic.

Let H 1 and H 2 be two skew heaps with N 1 and N 2 nodes, respectively, and let N be their
combined size (that is, N 1 + N 2 ). Suppose that the right path of H 1 has l 1 light nodes and
h 1 heavy nodes, for a total of l 1 + h 1 , whereas the right path of H 2 has l 2 light nodes and
h 2 heavy nodes, for a total of l 2 + h 2 . If the potential is defined as the total number of heavy
nodes in the collection of skew heaps, then the merge costs at most 2 log N + ( h 1 + h 2 ) ,
but the change in potential is at most 2 log N - ( h 1 + h 2 ) .

Theorem 23.1

The cost of the merge is merely the total number of nodes on the right paths,
l 1 + l 2 + h 1 + h 2 . The number of light nodes is logarithmic, so and
. Thus l 1 + l 2 ≤ log N 1 + log N 2 + 2 ≤ 2 log N , where the last inequality
follows from Theorem 22.4. The merge cost is thus at most 2 log N +( h 1 + h 2 ) . The
bound on the potential change follows from the fact that only the nodes involved in
the merge can have their heavy/light status changed and from the fact that any
heavy node on the path must become light because its children are swapped. Even if
all the light nodes became heavy, the potential change would still be limited to
l 1 + l 2 - ( h 1 + h 2 ) . Based on the same argument as before, that is at most
2 log N - ( h 1 + h 2 ) .

Proof

l 1 ≤ log N 1 + 1

l 2 ≤ log N 2 + 1