Skew Heaps

• A skew heap is a self-adjusting version of a 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 order, but there is no structural constraint on these trees.
• Unlike leftist heaps, no information is maintained about the null path length of any node.
• The right path of a skew heap can be arbitrarily long at any time, so the worst-case running time of all operations is O(N). However, as with splay trees, it can be shown that for any M consecutive operations, the total worst-case running time is O(M log N). Thus, skew heaps have O(log N) amortized cost per operation.
• As with leftist heaps, the fundamental operation on skew heaps is merging.
• The merge routine is once again recursive, and we perform the exact same operations as before, with one exception. 


  The difference is that for leftist heaps, we check to see whether the left and right children satisfy the leftist heap structure property and swap them if they do not. For skew heaps, the swap is unconditional; we always do it, with the one exception that the largest of all the nodes on the right paths does not have its children swapped.
• We can perform all operations nonrecursively, as with leftist heaps, by merging the right paths and swapping left and right children for every node on the right path, with the exception of the last. 


  It becomes clear that since all but the last node on the right path have their children swapped, the net effect is that this becomes the new left path.
• Skew heaps have the advantage that no extra space is required to maintain path lengths and no tests are required to determine when to swap children.