Page 228 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS
P. 228
Unit 11: Leftist Heaps and Binomial Queues
Figure 11.2: Merging Leftist Heaps Notes
Program 11.2 gives the code for the merge method of the LeftistHeap class. The merge method
makes use of two other methods, swapContents and swapSubtrees. The swapContents 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. 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
you are merging two trees, say T and T , with null path lengths d and d , respectively. Then the
1
2
2
1
running time of the merge method is
(d – 1 + d – 1)τ(isGT) + O(d + d )
1 2 1 2
LOVELY PROFESSIONAL UNIVERSITY 223
