Skew binomial heap

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.

[1] Ordinary binomial heaps suffer from worst case logarithmic complexity for insertion, because a carry operation may cascade, analogous to binary addition.

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

This allows the insertion operation to execute in constant time.

A skew binomial heap is a forest of skew binomial trees, which are defined inductively: When performing any link, the tree with the smallest key always becomes the root.

The following OCaml code demonstrates the linking operations: From these properties, it can be deduced that the root of a rank

The number of nodes in a skew binomial tree

Search the list of roots to find the node containing the minimum key.

In an imperative setting, one can maintain a pointer to the root containing the minimum key, allowing access in

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

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.

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: As up to one link is performed, this operation executes in worst case

time, improving on the binomial heap which relies on amortized analysis for its

Note that there may be more than two children with rank 0, due to skew links.

The children whose rank > 0 form a valid skew binomial heap, as they are already ordered, and have no duplicates.

Afterwards, reinsert each of the rank 0 children into the heap at a cost of

Repeatedly exchange it with its parent until the minimum-heap property is satisfied, at a cost of

This operation requires a pointer to the node containing the key in question, and is easiest done in an imperative setting.

Brodal and Okasaki showed how the time complexity of the merge operation can be reduced to

In the following OCaml code, the prime symbol ' denotes operations for bootstrapped heaps.

This technique can be applied to any priority queue with constant time insertion, and logarithmic merging.

Here are time complexities[3] of various heap data structures.