Page 227 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes public class LeftistHeap

extends BinaryTree
implements MergeablePriorityQueue
{
protected int nullPathLength;
//...
}

Program 11.1: LeftistHeap Fields
11.1.3 Merging Leftist Heaps

In order to merge two leftist heaps, say h1 and h2, declared as follows
MergeablePriorityQueue h1 = new LeftistHeap ();
MergeablePriorityQueue h2 = new LeftistHeap ();
I invoke the merge method like this:
h1.merge (h2);
The effect of the merge method is to take all the nodes from h2 and to attach them to h1, thus
leaving h2 as the empty heap.

In order to achieve a logarithmic running time, it is important for the merge method 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 you 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 you 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 you
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, I simply exchange the roles of h1 and h2 and proceed as
above.
Figure 11.2 illustrates the merge operation. In this example, I wish to merge the two trees T and
1
T shown in Figure 11.2 (a). Since T has the larger root, it is recursively merged with the right
2 2
subtree of T . The result of that merge replaces the right subtree of T as shown in Figure 11.2 (b).
1
1
Since the null path length of the right subtree is now greater than the left, the subtrees of T are
1
swapped giving the leftist heap shown in Figure 11.2 (c).

222 LOVELY PROFESSIONAL UNIVERSITY