Skew binomial heap should not be confused with Skew heap.
| Skew binomial heap | |
| Type: | heap |
| Invented Year: | 1996 |
| Invented By: | Gerth Stølting Brodal and Chris Okasaki |
| Insert Worst: | Θ(1) |
| Decrease Key Avg: | O(log n) |
| Delete Min Avg: | O(log n) |
| Insert Avg: | Θ(1) |
| Merge Avg: | O(log n) |
| Find Min Avg: | Θ(1) |
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.
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
2k+1-1
2k
A skew binomial heap is a forest of skew binomial trees, which are defined inductively:
r+1
r
r
r
r
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:
let simple_link (Tree (k1, r, c1) as t1) (Tree (k2, r, c2) as t2) = if k1 <= k2 then Tree (k1, r + 1, t2 :: c1) else Tree (k2, r + 1, t1 :: c2) let skew_link k1 (Tree (k2, r, c2) as t2) (Tree (k3, r, c3) as t3) = if k1 <= k2 && k1 <= k3 then (* type A *) Tree (k1, r + 1, [t2; t3]) else (* type B *) let t1 = Tree (k1, 0, []) in if k2 <= k3 then 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
2r
t
r
2r\le|t|\le2r+1-1
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.
Search the list of roots to find the node containing the minimum key. This takes
O(logn)
In an imperative setting, one can maintain a pointer to the root containing the minimum key, allowing access in
O(1)
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)
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(logn)
let rec merge_uniq h1 h2 = match h1, h2 with | h1, [] -> h1 | [], h2 -> h2 | t1 :: ts1, t2 :: ts2 -> if rank t1 < rank t2 then t1 :: merge_uniq ts1 h2 else if rank t1 > rank t2 then t2 :: merge_uniq h1 ts2 else unique (simple_link t1 t2 :: merge_uniq ts1 ts2) let merge h1 h2 = merge_uniq (unique h1) (unique h2)
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:
r
r+1
r+1
As up to one link is performed, this operation executes in worst case
O(1)
O(1)
O(logn)
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 to skew 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(logn)
O(1)
O(logn)
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 the minimum-heap property is satisfied, at a cost of
O(logn)
Brodal and Okasaki showed how the time complexity of the merge operation can be reduced to
O(1)
Let the type of a primitive skew binomial heap containing elements of type
\alpha
H\alpha
Let the type of a rooted skew binomial heap be
R\alpha=\alpha x
| H | |
| R\alpha |
that is, a pair containing an element of type
\alpha
Finally, we define the type of a bootstrapped heap by enclosing rooted heaps in an option type:
B\alpha=\{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.
let find_min' (Root (k, h)) = k
let merge' bh1 bh2 = match bh1, bh2 with | _, Empty -> bh1 | Empty, _ -> bh2 | Root (k1, h1), Root (k2, h2) -> if k1 <= k2 then Root (k1, insert bh2 h1) else Root (k2, insert bh1 h2)
let insert' k h = merge' (Root(k, [])) h
let delete_min' (Root (x, h)) = let Root (y, h1) = find_min h in let h2 = delete_min h in Root (y, merge h1 h2)
The new merge operation uses only insert operations on primitive heaps. Thus, it executes in
O(1)