notes throw new containeremptyexception ()comparable result (comparablegetkey ()leftistheap oldleft getleftheap ()leftistheap oldright getrightheap ()purge ()swapcontents (oldleft)merge (oldright)return result/program leftistheap class dequeuemin method the running time of program is determined by the time required to merge the two children of the root (line since the rest of the work in dequeuemin can be done in constant time consider the running time to delete the root of leftist heap with internal nodes the running time to merge the left and right subtrees of (dl dr ) (isgto(dl dr)where dl and dr are the null path lengths of the left and right subtrees trespectively in the worst casedr and dl log skew heaps there are several ways to implement heaps in self-adjusting fashion the one shall discuss is called skew heaps as proposed by sleator and tarjanand is analogous to leftist heaps skew heap is heap-ordered binary tree that isit is binary tree with one key in each node so that for each node other that the rootthe key at node is no less than the key at the parent of to represent such tree you store in each node its associated keydenoted key(xand two pointers left(xand right( )to its left child and right childrespectively if has no left child define left( =lif has no right child define right( = access to the tree is by pointer to its rootyou represent an empty tree by pointer to with this representation you can carry out the various heap operations as follows perform makeheap(hin ( time by initializing to since heap order implies that the root is minimum key in the treeyou can carry out findmin(hin ( time by returning the key at the rootreturning null if the heap is empty you perform insert and deletemin using union to carry out insert( ) make into one-node heap and union it with to carry out deletemin( )if is not empty replace by the union of its left and right subtrees and return the key at the original root (if is originally empty you return null to perform unionh )you form single tree by traversing down the right paths of and merging them into single right path with keys in nondecreasing order first assume the left subtrees of nodes along the merge path do not change (figure (athe time for the union operation is bounded by constant times the length of the merge path to make union efficientyou must keep right paths short in leftist heaps this is done by maintaining the invariant thatfor any node xthe right path descending from is shortest path down to missing node maintaining this invariant requires storing at every node the length of shortest path down to missing nodeafter the merge you walk back up the merge pathupdating the shortest path lengths and swapping left and right children as necessary to maintain the leftist property the length of the right path in leftist heap of nodes is at most log nimplying an olog lovely professional university