skew heaps skew heap is self-adjusting version of leftist heap that is incredibly simple to implement the relationship of skew heaps to leftist heaps is analogous to the relation between splay trees and avl trees skew heaps are binary trees with heap orderbut there is no structural constraint on these trees unlike leftist heapsno information is maintained about the null path length of any node the right path of skew heap can be arbitrarily long at any timeso the worst-case running time of all operations is (nhoweveras with splay treesit can be shown (see that for any consecutive operationsthe total worst-case running time is ( log nthusskew heaps have (log namortized cost per operation as with leftist heapsthe fundamental operation on skew heaps is merging the merge routine is once again recursiveand we perform the exact same operations as beforewith one exception the difference is that for leftist heapswe check to see whether the left and right children satisfy the leftist heap structure property and swap them if they do not for skew heapsthe swap is unconditionalwe always do itwith the one exception that the largest of all the nodes on the right paths does not have its children swapped this one exception is what happens in the natural recursive implementationso it is not really special case at all furthermoreit is not necessary to prove the boundsbut since this node is guaranteed not to have right childit would be silly to perform the swap and give it one (in our examplethere are no children of this nodeso we do not worry about it againsuppose our input is the same two heaps as beforefigure if we recursively merge with the subheap of rooted at we will get the heap in figure againthis is done recursivelyso by the third rule of recursion (section we need not worry about how it was obtained this heap happens to be leftistbut there is no guarantee that this is always the case we make this heap the new left child of and the old left child of becomes the new right child (see fig the entire tree is leftistbut it is easy to see that that is not always trueinserting into this new heap would destroy the leftist property we can perform all operations nonrecursivelyas with leftist heapsby merging the right paths and swapping left and right children for every node on the right pathwith figure two skew heaps and