Skew heap

Last updated August 07, 2023

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 search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree.

In computer science, a binary tree is a k-ary $tree data structure in which each node has at most two children, which are referred to as the left child and the right child . A recursive definition using just set theory notions is that a (non-empty) 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. Some authors allow the binary tree to be the empty set as well.$

In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent. These constraints mean there are no cycles or "loops", and also that each child can be treated like the root node of its own subtree, making recursion a useful technique for tree traversal. In contrast to linear data structures, many trees cannot be represented by relationships between neighboring nodes in a single straight line.

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

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 but also allows pairs of heaps to be merged. It is important as an implementation of the mergeable heap abstract data type, which is a priority queue supporting merge operation. 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.

In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree.

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.

<i>k</i>-d tree Multidimensional search tree for points in k dimensional space

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key and creating point clouds. k-d trees are a special case of binary space partitioning trees.

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.

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations:

In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers. The smallest number in the sequence is at the root of the tree; its left and right subtrees are constructed recursively from the subsequences to the left and right of this number. When all numbers are distinct, the Cartesian tree is uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree 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 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 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.

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]