In order to merge two leftist heaps, say `h1` and `h2`,
declared as follows

LeftistHeap h1; LeftistHeap h2;we invoke the

h1.Merge (h2);The effect of the

In order to achieve a logarithmic running time,
it is important for the `Merge` routine to do all its work
on the right sides of `h1` and `h2`.
It turns out that the algorithm for merging leftist heaps
is actually quite simple.

To begin with, if `h1` is the empty heap,
then we can simply swap the contents of `h1` and `h2`.
Otherwise, let us assume that the root of `h2` is larger than
the root of `h1`.
Then we can merge the two heaps by recursively merging `h2`
with the *right* subheap of `h1`.
After doing so, it may turn out that the right subheap of `h1`
now has a larger null path length than the left subheap.
This we rectify by swapping the left and right subheaps so that the result
is again leftist.
On the other hand, if `h2` initially has the smaller root,
we simply exchange the rôles of `h1` and `h2` and proceed as above.

Figure illustrates the merge operation. In this example, we wish to merge the two trees and shown in Figure (a). Since has the larger root, it is recursively merged with the right subtree of . The result of that merge replaces the right subtree of as shown in Figure (b). Since the null path length of the right subtree is now greater than the left, the subtrees of are swapped giving the leftist heap shown in Figure (c).

Program gives the code for the `Merge` member
function of the `LeftistHeap` class.
Clearly, the `Merge` routine only visits nodes on the rightmost paths
of the trees being merged.
Suppose we are merging two trees, say and ,
with null path lengths and , respectively.
Then the running time of the `Merge` routine is

where is time required to compare two keys. If we assume that the time to compare two keys is a constant, then we get , where and are the number of internal nodes in trees and , respectively.

**Program:** `LeftistHeap` Class `Merge` Member Function Definition

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.