This is the summary of skew heap part in MAW Chapter 6.
Like the relation between splay trees and AVL trees, we want to have \(O(\log N)\) amortized cost per operation. In addition, we don't want to have any auxiliary information stored at the nodes. In other words, we want to trade strict \(O(\log N)\) operation for less space we need to use for the data structure. In this case, like splay trees to AVL trees, we have Skew heaps to leftist heaps.
Skew heaps are binary trees with heap order, but there is no structural constraint on these trees. This means that we don't need the binary tree to be complete (i.e. binary heap) or left heavy (i.e. leftist heap).
In addition, we don't store \(Npl\) information in the node.
- A perfectly balanced tree forms if the keys \(1\) to \(2^k-1\) are inserted in order into an initially empty skew heap.
Skew heap is extremely similar with leftist heap
in terms of
merge operation. There is only one difference: for leftist heap, we check to see whether the
left and right children satisfy the leftist heap order property and swap them
if they do not. However, for skew heaps, the swap is unconditional. In other words,
we always swap the left & right subtrees at each step of merge.
In the below example, we want to merge two skew heaps \(H_1\) and \(H_2\):
Then, we get the following result of merging \(H_2\) with \(H_1\)'s right subheap:
and this is the final merge result:
The end result is actually leftist heap but there is no guaranteed that this is always the case. If you take a look, \(H_1\) is not lefist heap.
insertare all running in \(O(\log N)\) amortized time.
Links to resources
Here are some of the resources I found helpful while preparing this article:
- MAW Chapter 6
- CMU lecture slides