In computer science, a skew binomial heap (or skew binomial queue) 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.
Motivation Just as binomial heaps are based on the binary number system, skew binary heaps are based on the skew binary number system. Ordinary binomial heaps suffer from worst case logarithmic complexity for insertion, because a carry operation may cascade, analogous to binary addition. Skew binomial heaps are based on the skew binary number system, where the k {\displaystyle k} th digit (zero-indexed) represents 2 k + 1 − 1 {\displaystyle 2^{k+1}-1} , instead of 2 k {\displaystyle 2^{k}} . Digits are either 0 or 1, except the lowest non-zero digit, which may be 2. An advantage of this system is that at most one carry operation is needed. For example, 60 is represented as 11200 in skew binary (31 + 15 + 7 + 7), and adding 1 produces 12000 (31 + 15 + 15). Since the next higher digit is guaranteed not to be 2, a carry is performed at most once. This analogy is applied to the insertion operation by introducing ternary (skew) links, which link 3 trees together. This allows the insertion operation to execute in constant time.
Structure
A skew binomial heap is a forest of skew binomial trees, which are defined inductively:
A skew binomial tree of rank 0 is a singleton node. A skew binomial tree of rank r + 1 {\displaystyle r+1} can be constructed in three ways: a simple link links two rank r {\displaystyle r} trees, making one the leftmost child of the other; a type A skew link links three trees. Two rank r {\displaystyle r} trees become the children of a rank 0 tree; a type B skew link links three trees. A rank 0 tree and rank r {\displaystyle r} tree become the leftmost children of another rank r {\displaystyle r} tree. When performing any link, the tree with the smallest key always becomes the root. Additionally, we impose the invariant that there may be only one tree of each rank, except the lowest rank which may have up to two. The following OCaml code demonstrates the linking operations:
From these properties, it can be deduced that the root of a rank r {\displaystyle r} skew binomial tree has up to 2 r {\displaystyle 2r} children. The number of nodes in a skew binomial tree t {\displaystyle t} of rank r {\displaystyle r} is also bounded by 2 r ≤ | t | ≤ 2 r + 1 − 1 {\displaystyle 2^{r}\leq |t|\leq 2^{r+1}-1} . Since trees of the same rank may have different numbers of nodes, there may be more than one way to distribute the ranks in the heap. These constructions may be seen as a generalisation of binary trees and binomial trees. A skew binomial tree constructed using only simple links is an ordinary binomial tree, and using only type A skew links results in a perfectly balanced binary tree.
Operations
Find-min Search the list of roots to find the node containing the minimum key. This takes O ( log n ) {\displaystyle O(\log n)} time. In an imperative setting, one can maintain a pointer to the root containing the minimum key, allowing access in O ( 1 ) {\displaystyle O(1)} time. This pointer must be updated after every operation, adding only a constant overhead in time complexity. In a functional setting without random access to nodes, one can instead represent the heap as a single tree with skew binomial trees as its children. The root of this tree is the minimum of the heap, allowing O ( 1 ) {\displaystyle O(1)} access. Note that this tree will not necessarily be a skew binomial tree itself. The other operations must be modified to deal with this single tree. This concept of a global root is used in the optimizations described below, albeit slightly differently.
Merge To merge two skew binomial heaps together, first eliminate any duplicate rank trees in each heap by performing simple links. Then, merge the heaps in the same fashion as ordinary binomial heaps, which is similar to binary addition. Trees with the same ranks are linked with a simple link, and a 'carry' tree is passed upwards if necessary. Because the rank of trees in each heap is now unique, at most three trees of the same rank are considered, which is sufficient to establish a O ( log n ) {\displaystyle O(\log n)} bound.
Insert Create a skew binomial tree of rank 0 (a singleton node), containing the key to be inserted. The smallest two trees in the heap are then considered:
… excerpt ends here. Continue reading the full article.
