stringtranslate.com

Skew heap

A skew heap (or self-adjusting heap) is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic. Only two conditions must be satisfied:

A skew heap is a self-adjusting form of a leftist heap which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. (The merge operation is also used when adding and removing values.) With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, amortized complexity analysis can be used to demonstrate that all operations on a skew heap can be done in O(log n).[1]In fact, with denoting the golden ratio, the exact amortized complexity is known to be logφ n (approximately 1.44 log2 n).[2][3]

Definition

Skew heaps may be described with the following recursive definition:[citation needed][clarification needed]

Operations

Merging two heaps

When two skew heaps are to be merged, we can use a similar process as the merge of two leftist heaps:


template<class T, class CompareFunction>SkewNode<T>* CSkewHeap<T, CompareFunction>::Merge(SkewNode<T>* root_1, SkewNode<T>* root_2){ SkewNode<T>* firstRoot = root_1; SkewNode<T>* secondRoot = root_2; if (firstRoot == NULL) return secondRoot; else if (secondRoot == NULL) return firstRoot; if (sh_compare->Less(firstRoot->key, secondRoot->key)) { SkewNode<T>* tempHeap = firstRoot->rightNode; firstRoot->rightNode = firstRoot->leftNode; firstRoot->leftNode = Merge(secondRoot, tempHeap); return firstRoot; } else return Merge(secondRoot, firstRoot);}

Before:


after

Non-recursive merging

Alternatively, there is a non-recursive approach which is more wordy, and does require some sorting at the outset.

Adding values

Adding a value to a skew heap is like merging a tree with one node together with the original tree.

Removing values

Removing the first value in a heap can be accomplished by removing the root and merging its child subtrees.

Implementation

In many functional languages, skew heaps become extremely simple to implement. Here is a complete sample implementation in Haskell.

data SkewHeap a = Empty | Node a (SkewHeap a) (SkewHeap a)singleton :: Ord a => a -> SkewHeap asingleton x = Node x Empty Emptyunion :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap aEmpty `union` t2 = t2t1 `union` Empty = t1t1@(Node x1 l1 r1) `union` t2@(Node x2 l2 r2) | x1 <= x2 = Node x1 (t2 `union` r1) l1 | otherwise = Node x2 (t1 `union` r2) l2insert :: Ord a => a -> SkewHeap a -> SkewHeap ainsert x heap = singleton x `union` heapextractMin :: Ord a => SkewHeap a -> Maybe (a, SkewHeap a)extractMin Empty = NothingextractMin (Node x l r) = Just (x, l `union` r)

References

  1. ^ Sleator, Daniel Dominic; Tarjan, Robert Endre (February 1986). "Self-Adjusting Heaps". SIAM Journal on Computing. 15 (1): 52–69. CiteSeerX 10.1.1.93.6678. doi:10.1137/0215004. ISSN 0097-5397.
  2. ^ Kaldewaij, Anne; Schoenmakers, Berry (1991). "The Derivation of a Tighter Bound for Top-Down Skew Heaps" (PDF). Information Processing Letters. 37 (5): 265–271. CiteSeerX 10.1.1.56.8717. doi:10.1016/0020-0190(91)90218-7.
  3. ^ Schoenmakers, Berry (1997). "A Tight Lower Bound for Top-Down Skew Heaps" (PDF). Information Processing Letters. 61 (5): 279–284. CiteSeerX 10.1.1.47.447. doi:10.1016/S0020-0190(97)00028-8. S2CID 11288837.

External links