figure leftist heap notes the reason for our interest in leftist trees is illustrated by the following theoremstheorem- consider leftist tree which contains internal nodes the path leading from the root of downwards to the rightmost external node contains at most log ( nodes extbfproof assume that has null path length then must contain at least - leaves otherwisethere would be shorter path than from the root of to an external node binary tree with exactly leaves has exactly - non-leaf internal nodes since has at least - leavesit must contain at least > internal nodes altogether therefored <log ( since is leftist treethe shortest path to an external node must be the path on the right thusthe length of the path to the rightmost external is at most log ( there is an interesting dichotomy between avl balanced trees and leftist trees the shape of an avl tree satisfies the avl balance condition which stipulates that the difference in the heights of the left and right subtrees of every node may differ by at most one the effect of avl balancing is to ensure that the height of the tree is (log non the other handleftist trees have an ``imbalance condition'which requires the null path length of the left subtree to be greater than or equal to that of the right subtree the effect of the condition is to ensure that the length of the right path in leftist tree is (log nthereforeby devising algorithms for manipulating leftist heaps which only follow the right path of the heapyou can achieve running times which are logarithmic in the number of nodes the dichotomy also extends to the structure of the algorithms for examplean imbalance sometimes results from an insertion in an avl tree the imbalance is rectified by doing rotations similarlyan insertion into leftist tree may result in violation of the ``imbalance condition 'that isthe null path length of the right subtree of node my become greater than that of the left subtree fortunatelyit is possible to restore the proper condition simply by swapping the left and right subtrees of that node implementation this section presents an implementation of leftist heaps that is based on the binary tree implementation program introduces the leftistheap class the leftistheap class extends the binarytree class introduced in program and it implements the mergeablepriorityqueue interface defined in program lovely professional university