priority queues (heapsthe node referenced by the root will need to change we use the usual technique of implementing private recursive methods to do the merging the class skeleton is also shown in figure the two merge routines (fig are drivers designed to remove special cases and ensure that has the smaller root the actual merging is performed in merge (fig the public merge method merges rhs into the controlling heap rhs becomes empty the alias test in the public method disallows merge(hthe time to perform the merge is proportional to the sum of the length of the right pathsbecause constant work is performed at each node visited during the recursive calls thus we obtain an (log ntime bound to merge two leftist heaps we can also perform this operation nonrecursively by essentially performing two passes in the first passwe create new tree by merging the right paths of both heaps to do thiswe arrange the nodes on the right paths of and in sorted orderkeeping their respective left children in our examplethe new right path is and the resulting tree is shown in figure /*merge rhs into the priority queue rhs becomes empty rhs must be different from this *void mergeleftistheap rhs ifthis =&rhs /avoid aliasing problems returnroot mergerootrhs root )rhs root nullptr/*internal method to merge two roots deals with deviant cases and calls recursive merge *leftistnode mergeleftistnode * leftistnode * ifh =nullptr return ifh =nullptr return ifh ->element element return merge )else return merge )figure driving routines for merging leftist heaps