function SkewedHeapMerge(h,h) :

heap if h is empty then return h'

else if h' is empty then return h

if the root of h' the root of h then exchange h and h' (* h holds smallest root *)

if right(h) = nil

then right(h) := h' (* last node, we don't swap *)

else right(h) := SkewedHeapMerge(right(h), h')

swap left and right children of h

return h

The above recursive routine can also be done iteratively. In fact, it can be done more eciently than the leftist heap Merge (by a constant factor), because everything can be done in one pass, while moving down the rightmost path. In the case of leftist heaps, we go down the rightmost path, and then back up to recompute ranks. In leftist heaps, that also requires either a recursive algorithm or pointers from nodes to their parents. Since there is no balance condition, there's no guarantee that these trees will have O(log n) worst-case performance for the merge (and hence all of the other operations). But they do have good amortized performance. Here's the intuition for the above: In the previous merge algorithm we only had to swap children when the right one had a larger rank than the left. In this merge algorithm, we always swap children, so we might actually replace a right child of "small" rank with one of "large" rank. But the next time we come down this path, we will correct that error, because the right child will be swapped onto the left.

(a) Show that a SkewedHeapMerge of two skewed heaps uses amortized time O(log₂n) by the use of the accounting method.

(b) Show that Insert and DeleteMin have the same amortized time bounds.