Skew heap

Last updated May 30, 2024

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 ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ denoting the golden ratio, the exact amortized complexity is known to be log_φn (approximately 1.44 log₂n).^[2]^[3]

Definition

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

A heap with only one element is a skew heap.
The result of skew merging two skew heaps $sh_{1}$ and $sh_{2}$ is also a skew heap.

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:

Compare roots of two heaps; let p be the heap with the smaller root, and q be the other heap. Let r be the name of the resulting new heap.
Let the root of r be the root of p (the smaller root), and let r's right subtree be p's left subtree.
Now, compute r's left subtree by recursively merging p's right subtree with q.

template<classT,classCompareFunction>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)returnsecondRoot;elseif(secondRoot==NULL)returnfirstRoot;if(sh_compare->Less(firstRoot->key,secondRoot->key)){SkewNode<T>*tempHeap=firstRoot->rightNode;firstRoot->rightNode=firstRoot->leftNode;firstRoot->leftNode=Merge(secondRoot,tempHeap);returnfirstRoot;}elsereturnMerge(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.

Split each heap into subtrees by cutting every path. (From the root node, sever the right node and make the right child its own subtree.) This will result in a set of trees in which the root either only has a left child or no children at all.
Sort the subtrees in ascending order based on the value of the root node of each subtree.
While there are still multiple subtrees, iteratively recombine the last two (from right to left).
- If the root of the second-to-last subtree has a left child, swap it to be the right child.
- Link the root of the last subtree as the left child of the second-to-last subtree.

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.

dataSkewHeapa=Empty|Nodea(SkewHeapa)(SkewHeapa)singleton::Orda=>a->SkewHeapasingletonx=NodexEmptyEmptyunion::Orda=>SkewHeapa->SkewHeapa->SkewHeapaEmpty`union`t2=t2t1`union`Empty=t1t1@(Nodex1l1r1)`union`t2@(Nodex2l2r2)|x1<=x2=Nodex1(t2`union`r1)l1|otherwise=Nodex2(t1`union`r2)l2insert::Orda=>a->SkewHeapa->SkewHeapainsertxheap=singletonx`union`heapextractMin::Orda=>SkewHeapa->Maybe(a,SkewHeapa)extractMinEmpty=NothingextractMin(Nodexlr)=Just(x,l`union`r)

Related Research Articles

<span class="mw-page-title-main">AVL tree</span> Self-balancing binary search tree

In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take $O(log n)$ time in both the average and worst cases, where $is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.$

In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree with $k = 2$ . A recursive definition using set theory is that a binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.

In computer science, a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time. Compared to other self-balancing binary search trees, the nodes in a red-black tree hold an extra bit called "color" representing "red" and "black" which is used when re-organising the tree to ensure that it is always approximately balanced.

<span class="mw-page-title-main">Binary heap</span> Variant of heap data structure

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.

<span class="mw-page-title-main">Treap</span> Random search tree data structure

In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.

In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap, as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

In computer science, tree traversal is a form of graph traversal and refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well.

In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less than any keys in subtrees on the right.

An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named after their originator, Swedish computer scientist Arne Andersson.

In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value.

A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations :

In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionaries (maps) and sequences. These trees were introduced by Nievergelt and Reingold in the 1970s as trees of bounded balance, or BB[α] trees. Their more common name is due to Knuth.

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of $but worse storage of, where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.$

In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.

In computer science, a min-max heap is a complete binary tree data structure which combines the usefulness of both a min-heap and a max-heap, that is, it provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it. This makes the min-max heap a very useful data structure to implement a double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support logarithmic insertion and deletion and can be built in linear time. Min-max heaps are often represented implicitly in an array; hence it's referred to as an implicit data structure.

In computer science, a skew binomial heap is a data structure for priority queue operations. It is a variant of the binomial heap that supports constant-time insertion operations in the worst case, rather than amortized time.

In computer science, a randomized meldable heap is a priority queue based data structure in which the underlying structure is also a heap-ordered binary tree. However, there are no restrictions on the shape of the underlying binary tree.

In the mathematical field of graph theory, an agreement forest for two given trees is any forest which can, informally speaking, be obtained from both trees by removing a common number of edges.

In computer science, a weak heap is a data structure for priority queues, combining features of the binary heap and binomial heap. It can be stored in an array as an implicit binary tree like a binary heap, and has the efficiency guarantees of binomial heaps.

In computer science, join-based tree algorithms are a class of algorithms for self-balancing binary search trees. This framework aims at designing highly-parallelized algorithms for various balanced binary search trees. The algorithmic framework is based on a single operation join. Under this framework, the join operation captures all balancing criteria of different balancing schemes, and all other functions join have generic implementation across different balancing schemes. The join-based algorithms can be applied to at least four balancing schemes: AVL trees, red–black trees, weight-balanced trees and treaps.

References

↑ 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.
↑ 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.
↑ 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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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.

[1]

[2]

[3]