Skew binomial heap

Not to be confused withSkew heap.

Skew binomial heap
Type	heap
Invented	1996
Invented by	Gerth Stølting BrodalandChris Okasaki
Time complexityinbig O notation Operation Average Worst case Insert Θ(1) Θ(1) Find-min Θ(1) Delete-min O(logn) Decrease-key O(logn) Merge O(logn) Space complexity

Incomputer science,askew binomial heap(orskew binomial queue) is adata structureforpriority queueoperations. It is a variant of thebinomial heapthat supports constant-time insertion operations in the worst case, rather thanamortized time.

Motivation

Just asbinomial heapsare based on thebinary number system,skew binary heaps are based on theskew binary number system.Ordinary binomial heaps suffer from worst case logarithmic complexity for insertion, because acarryoperation may cascade, analagous to binary addition. Skew binomial heaps are based on the skew binary number system, where the$k$th digit (zero-indexed) represents$2^{k+1}-1$,instead of$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

Skew binomial heap containing numbers 1 to 19, showing trees of ranks 0, 1, 2, and 3 constructed from various types of links

Simple, typeaskew, and typebskew links

A skew binomial heap is aforestof skew binomialtrees,which are defined inductively:

• A skew binomial tree of rank 0 is a singleton node.
• A skew binomial tree of rank$r+1$can be constructed in three ways:
  • asimple linklinks two rank$r$trees, making one the leftmost child of the other;
  • atype A skew linklinks three trees. Two rank$r$trees become the children of a rank 0 tree;
  • atype B skew linklinks three trees. A rank 0 tree and rank$r$tree become the leftmost children of another rank$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 followingOCamlcode demonstrates the linking operations:

type'aheap='atreelist
and'atree=Treeof'a*int*'atreelist

letrank(Tree(_,r,_))=r

letsimple_link(Tree(k1,r,c1)ast1)(Tree(k2,r,c2)ast2)=
ifk1<=k2then
Tree(k1,r+1,t2::c1)
else
Tree(k2,r+1,t1::c2)

letskew_linkk1(Tree(k2,r,c2)ast2)(Tree(k3,r,c3)ast3)=
ifk1<=k2&&k1<=k3then(* type A *)
Tree(k1,r+1,[t2;t3])
else(* type B *)
lett1=Tree(k1,0,[])in
ifk2<=k3then
Tree(k2,r+1,t1::t3::c2)
else
Tree(k3,r+1,t1::t2::c3)

From these properties, it can be deduced that the root of a rank$r$skew binomial tree has up to$2r$children. The number of nodes in a skew binomial tree$t$of rank$r$is also bounded by$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 ofbinary treesand binomial trees. A skew binomial tree constructed using onlysimple linksis an ordinary binomial tree, and using onlytype A skew linksresults 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)$time.

In an imperative setting, one can maintain a pointer to the root containing the minimum key, allowing access in$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)$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 theoptimizationsdescribed below, albeit slightly differently.

Merge

To merge two skew binomial heaps together, first eliminate any duplicate rank trees in each heap by performingsimple 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 asimple 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)$bound.

letrecunique=function
|t1::t2::tswhenrankt1=rankt2->
unique(simple_linkt1t2::ts)
|ts->ts

letrecmerge_uniqh1h2=matchh1,h2with
|h1,[]->h1
|[],h2->h2
|t1::ts1,t2::ts2->
ifrankt1<rankt2then
t1::merge_uniqts1h2
elseifrankt1>rankt2then
t2::merge_uniqh1ts2
else
unique(simple_linkt1t2::merge_uniqts1ts2)

letmergeh1h2=merge_uniq(uniqueh1)(uniqueh2)

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:

• If they are both of rank$r$,then perform askew linkwith these two trees and the singleton node. The resulting tree is of rank$r+1$.Since there can only have been at most one rank$r+1$tree in the original heap, the invariant is preserved.
• If they are of different ranks, simply add the rank 0 tree to the front of the list of roots. Since the list of roots did not have duplicate rank trees before, the invariant is not violated, as there will be at most two rank 0 trees after.

As up to one link is performed, this operation executes in worst case$O(1)$time, improving on the binomial heap which relies onamortizedanalysis for its$O(1)$bound, with a worst case of$O(\log n)$.

letinsertk=function
|t2::t3::tswhenrankt2=rankt3->skew_linkkt2t3::ts
|ts->Tree(k,0,[])::ts

Delete-min

Find and discard the node containing the minimum key. This node must be the root of a tree. Divide its children into two groups, those with rank 0, and those with rank > 0. Note that there may be more than two children with rank 0, due toskew links.The children whose rank > 0 form a valid skew binomial heap, as they are already ordered, and have no duplicates. Merging these children into the heap takes$O(\log n)$time. Afterwards, reinsert each of the rank 0 children into the heap at a cost of$O(1)$each. The total time required is$O(\log n)$.

Decrease-key

This operation is unchanged from binomial heaps. Decreasing the key of a node may cause it to be smaller than its parent. Repeatedly exchange it with its parent until theminimum-heapproperty is satisfied, at a cost of$O(\log n)$time complexity. This operation requires a pointer to the node containing the key in question, and is easiest done in an imperative setting.

Optimizations

Brodal and Okasaki showed how the time complexity of the merge operation can be reduced to$O(1)$,by applying the 'bootstrapping' technique of Buchsbaum andTarjan.

Let the type of a primitive skew binomial heap containing elements of type$\alpha$be$H_{\alpha }$.Instead of the forest of trees representation described above, we mainintain a single tree with a global root as its minimum.

Let the type of arootedskew binomial heap be

$R_{\alpha }=\alpha \times H_{R_{\alpha }}$,

that is, a pair containing an element of type$\alpha$and a primitive heap of rooted heaps.

Finally, we define the type of abootstrapped heapby enclosing rooted heaps in anoption type:

$B_{\alpha }=\{\mathrm {Empty} \}+R_{\alpha }$

which permits the empty heap.

The operations on this bootstrapped heap are redefined accordingly. In the following OCaml code, the prime symbol'denotes operations for bootstrapped heaps.

type'abootstrapped=
|Empty
|Rootof'arooted

letfind_min'(Root(k,h))=k

letmerge'bh1bh2=matchbh1,bh2with
|_,Empty->bh1
|Empty,_->bh2
|Root(k1,h1),Root(k2,h2)->
ifk1<=k2then
Root(k1,insertbh2h1)
else
Root(k2,insertbh1h2)

letinsert'kh=merge'(Root(k,[]))h

letdelete_min'(Root(x,h))=
letRoot(y,h1)=find_minhin
leth2=delete_minhin
Root(y,mergeh1h2)

The new merge operation uses only insert operations on primitive heaps. Thus, it executes in$O(1)$time. This technique can be applied to any priority queue with constant time insertion, and logarithmic merging.

Summary of running times

Here aretime complexitiesof various heap data structures. The abbreviationam.indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f) "and"Θ(f) "seeBig O notation.Names of operations assume a min-heap.

Operation	find-min	delete-min	decrease-key	insert	meld	make-heap
Binary	Θ(1)	Θ(logn)	Θ(logn)	Θ(logn)	Θ(n)	Θ(n)
Skew	Θ(1)	O(logn)am.	O(logn)am.	O(logn)am.	O(logn)am.	Θ(n)am.
Leftist	Θ(1)	Θ(logn)	Θ(logn)	Θ(logn)	Θ(logn)	Θ(n)
Binomial	Θ(1)	Θ(logn)	Θ(logn)	Θ(1)am.	Θ(logn)	Θ(n)
Skew binomial	Θ(1)	Θ(logn)	Θ(logn)	Θ(1)	Θ(logn)	Θ(n)
2–3 heap	Θ(1)	O(logn)am.	Θ(1)	Θ(1)am.	O(logn)	Θ(n)
Bottom-up skew	Θ(1)	O(logn)am.	O(logn)am.	Θ(1)am.	Θ(1)am.	Θ(n)am.
Pairing	Θ(1)	O(logn)am.	o(logn)am.	Θ(1)	Θ(1)	Θ(n)
Rank-pairing	Θ(1)	O(logn)am.	Θ(1)am.	Θ(1)	Θ(1)	Θ(n)
Fibonacci	Θ(1)	O(logn)am.	Θ(1)am.	Θ(1)	Θ(1)	Θ(n)
Strict Fibonacci	Θ(1)	Θ(logn)	Θ(1)	Θ(1)	Θ(1)	Θ(n)
Brodal	Θ(1)	Θ(logn)	Θ(1)	Θ(1)	Θ(1)	Θ(n)