priority queues (heaps figure null path lengths for two treesonly the left tree is leftist proof the proof is by induction if there must be at least one tree node otherwisesuppose that the theorem is true for consider leftist tree with nodes on the right path then the root has right subtree with nodes on the right pathand left subtree with at least nodes on the right path (otherwise it would not be leftistapplying the inductive hypothesis to these subtrees yields minimum of nodes in each subtree this plus the root gives at least + nodes in the treeproving the theorem from this theoremit follows immediately that leftist tree of nodes has right path containing at most log( nodes the general idea for the leftist heap operations is to perform all the work on the right pathwhich is guaranteed to be short the only tricky part is that performing inserts and merges on the right path could destroy the leftist heap property it turns out to be extremely easy to restore the property leftist heap operations the fundamental operation on leftist heaps is merging notice that insertion is merely special case of mergingsince we may view an insertion as merge of one-node heap with larger heap we will first give simple recursive solution and then show how this might be done nonrecursively our input is the two leftist heapsh and in figure you should check that these heaps really are leftist notice that the smallest elements are at the roots in addition to space for the data and left and right pointerseach node will have an entry that indicates the null path length if either of the two heaps is emptythen we can return the other heap otherwiseto merge the two heapswe compare their roots firstwe recursively merge the heap with the larger root with the right subheap of the heap with the smaller root in our examplethis means we recursively merge with the subheap of rooted at obtaining the heap in figure since this tree is formed recursivelyand we have not yet finished the description of the algorithmwe cannot at this point show how this heap was obtained howeverit is