A practice problem in my textbook asks to proof the amortized complexity for a sequence of insert, delete min, and decrease-key operations on an initially empty skew heap. Insert and delete min both have an amortized complexity of $O(log(n))$, and the deletion algorithm that removes an arbitrary node in a skew heap is defined as:

The subtree $ S_v $ with root $v$ is removed from the heap. Then the path from $v$ to the root (of the tree) is traversed. If a vertex on that path has $v$ in its left subtree and has a right child, then its children are swapped. This way the result remains a skew heap. The root of $ S_v $ is removed by the delete min operation, the left and right subtree of $v$ get merged, and that result gets merged with the initial tree.

I get that I'll have to use either the potential method or the accounting method, and I use the definitions for heavy and light edges (the original paper about skew heaps uses this definition for nodes instead):

"Take any node $v$ with its child $c$; we call the edge from $v$ to $c$ heavy, if size of $c$’s subtree is more than half the size of $v$’s subtree, or in other words, more than half of the descendants of $v$ are under $c$ . Otherwise we call the edge ($v$,$c$) light."

I don't really get how I should account for the traversal from $v$ to the root that takes place during the arbitrary deletion algorithm in my analysis though.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.