Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

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();
we 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 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 roles of h1 and h2 and proceed as above.

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

   figure25507
Figure: Merging leftist heaps.

Program gif gives the code for the Merge method of the LeftistHeap class. The Merge method makes use of two other methods, SwapContentsWith and SwapSubtrees. The SwapContentsWith method takes as its argument a leftist heap, and exchanges all the contents (key and subtrees) of this heap with the given one. The SwapSubtrees method exchanges the left and right subtrees of this node. The implementation of these routines is trivial and is left as a project for the reader (Project gif). Clearly, the worst-case running time for each of these routines is O(1).

The Merge method only visits nodes on the rightmost paths of the trees being merged. Suppose we are merging two trees, say tex2html_wrap_inline62549 and tex2html_wrap_inline62551, with null path lengths tex2html_wrap_inline65671 and tex2html_wrap_inline65673, respectively. Then the running time of the Merge method is

displaymath65647

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

   program25896
Program: LeftistHeap class Merge method.


next up previous contents index

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