Skew binomial heap

A binomial heap stores $n$ elements as a list of trees whose sizes are the powers of two in the binary representation of $n$ ^[3]. Inserting an element is incrementing a binary number: a carry can ripple through every digit, so one insertion may link $lo g_{2} n$ trees. A skew binomial heap uses skew binary numbers instead, in which an increment changes at most two digits, so insertion does at most one link^[1]^[2].

§ 01

Skew binary numbers

In skew binary, the $k$ -th digit has weight $2^{k + 1} - 1$ and the digits are 0, 1 or 2, with only the lowest non-zero digit allowed to be 2^[4]^[5]. Every natural number has exactly one such representation:

n = \sum_{k} d_{k} (2^{k + 1} - 1) 1 + 2 (2^{k + 1} - 1) = 2^{k + 2} - 1

The second identity is the whole trick. If the lowest non-zero digit is a 2, incrementing turns it into 0 and adds one to the next digit; otherwise it adds one to the lowest digit. Neither case propagates further.

§ 02

Trees and operations

A skew binomial tree of rank $r$ has $2^{r}$ nodes, each holding one element, and its root also holds a list of at most $r$ extra elements. A heap is a list of trees in increasing order of rank, where only the first two may have the same rank. Insertion looks at the first two trees: if their ranks are equal, a skew link makes them children of a new rank $r + 1$ tree rooted at the smallest of the three roots, with the new element stored among the extras if it is not the smallest; otherwise the element becomes a new tree of rank 0^[1]^[2].

A skew binomial heap in OCaml, following Okasaki.

(* A skew binomial heap: a list of trees in increasing order of rank,
   in which only the two smallest ranks may be equal. Each node keeps a
   list of up to r extra elements besides its children. *)
type 'a tree = Node of int * 'a * 'a list * 'a tree list
type 'a heap = 'a tree list
 
let links = ref 0
let rank (Node (r, _, _, _)) = r
let root (Node (_, x, _, _)) = x
 
let link (Node (r, x1, xs1, c1) as t1) (Node (_, x2, xs2, c2) as t2) =
  incr links;
  if x1 <= x2 then Node (r + 1, x1, xs1, t2 :: c1) else Node (r + 1, x2, xs2, t1 :: c2)
 
(* Link two trees of rank r under a new element: a tree of rank r + 1. *)
let skew_link x t1 t2 =
  let (Node (r, y, ys, c)) = link t1 t2 in
  if x <= y then Node (r, x, y :: ys, c) else Node (r, y, x :: ys, c)
 
let insert x = function
  | t1 :: t2 :: rest when rank t1 = rank t2 -> skew_link x t1 t2 :: rest
  | ts -> Node (0, x, [], []) :: ts
 
let rec ins_tree t = function
  | [] -> [ t ]
  | t' :: ts -> if rank t < rank t' then t :: t' :: ts else ins_tree (link t t') ts
 
let rec merge_trees ts1 ts2 =
  match (ts1, ts2) with
  | ts, [] | [], ts -> ts
  | t1 :: ts1', t2 :: ts2' ->
      if rank t1 < rank t2 then t1 :: merge_trees ts1' ts2
      else if rank t2 < rank t1 then t2 :: merge_trees ts1 ts2'
      else ins_tree (link t1 t2) (merge_trees ts1' ts2')
 
let normalize = function [] -> [] | t :: ts -> ins_tree t ts
let merge h1 h2 = merge_trees (normalize h1) (normalize h2)
 
let rec remove_min_tree = function
  | [] -> raise Not_found
  | [ t ] -> (t, [])
  | t :: ts ->
      let t', ts' = remove_min_tree ts in
      if root t <= root t' then (t, ts) else (t', t :: ts')
 
let find_min h = root (fst (remove_min_tree h))
 
let delete_min h =
  let Node (_, _, xs, c), rest = remove_min_tree h in
  List.fold_left (fun h x -> insert x h) (merge (List.rev c) rest) xs

Merging first normalizes both lists, removing the duplicate rank at the front, and then merges them as binomial heaps. delete_min removes the tree with the smallest root, merges its children back in, and reinserts the extra elements one at a time. Both take $O (lo g n)$ time, and so does find_min, which scans the roots.

The largest number of links done by a single insertion, against an ordinary binomial heap, and a heapsort.

open Skew
 
(* Ordinary binomial insertion, for comparison: add a rank-0 tree and
   carry, like incrementing a binary number. *)
let binomial_insert x h = ins_tree (Node (0, x, [], [])) h
 
let worst name insert n =
  let h = ref [] and worst = ref 0 in
  for i = 1 to n do
    links := 0;
    h := insert i !h;
    worst := max !worst !links
  done;
  Printf.printf "%-9s %d inserts: at most %2d links in one insert, ranks %s\n" name n !worst
    (String.concat " " (List.map (fun t -> string_of_int (rank t)) !h))

Running it.

binomial  65535 inserts: at most 15 links in one insert, ranks 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
skew      65535 inserts: at most  1 links in one insert, ranks 15
3 9 9 31 37 41 42 43 44 53 57 57 58 58 60 72 82 88 90 96

With $65535 = 2^{16} - 1$ elements, the binomial heap has one tree for each of the 16 binary digits, and its worst insertion, of the 32,768th element, linked 15 trees. The skew heap never linked more than once per insertion, and since 65535 is a single skew digit, $2^{16} - 1$ , it is one tree of rank 15.

§ 03

History

Vuillemin introduced binomial queues in 1978^[3]. Myers used skew binary numbers in 1983 for a random-access stack^[4], and Okasaki used them in 1995 for purely functional random-access lists with constant-time cons^[5]. Brodal and Okasaki combined skew binomial trees with two further transformations in 1996: storing the minimum separately makes find_min constant time, and data-structural bootstrapping makes merge constant time, giving a purely functional priority queue whose bounds match the best imperative ones^[1].