Leftist heap

A leftist heap is a priority queue that supports merging two queues in logarithmic time^[1]^[2]. It is a binary tree in heap order, every node's element being no larger than its children's, with an additional shape condition: at every node, the right spine of the left child, the path that keeps going right, is at least as long as the right spine of the right child. The tree is therefore unbalanced towards the left, possibly very much so, but its right spine is short: it has at most $lo g_{2} (n + 1)$ nodes. Merging two heaps walks down their right spines, as when merging two sorted lists, and restores the shape condition on the way back up. Insertion merges a one-element heap, and deleting the minimum merges the root's two children. The operations never modify a tree in place and copy only the nodes on the right spines, which makes leftist heaps a standard persistent priority queue in functional programming^[3].

§ 01

Definition

The rank $r (t)$ of a tree, called dist in Knuth's presentation and the s-value in some texts, is the number of nodes on its right spine, with $r (\emptyset) = 0$ for the empty tree. A leftist heap is a binary tree that is heap-ordered and satisfies, at every node with children $a$ and $b$ ,

r (a) \geq r (b) r (node (x, a, b)) = r (b) + 1

Every node stores its rank so that the condition can be checked in constant time. A node with one child always has it on the left.

A leftist heap of seven elements, with the rank of each node. At every node the left child's rank is at least the right child's. The right spine, 1 then 3, has two nodes, although the tree has height four.

§ 02

The right spine is short

A tree of rank $r$ has at least $2^{r} - 1$ nodes. For $r = 0$ this holds trivially. A node of rank $r \geq 1$ has a right child of rank $r - 1$ and, by the leftist condition, a left child of rank at least $r - 1$ , so by induction it has at least

1 + 2 (2^{r - 1} - 1) = 2^{r} - 1

nodes. Hence a leftist heap of $n$ elements has rank at most $⌊ lo g_{2} (n + 1)⌋$ . Nothing bounds the height: the left spine can have $n$ nodes^[2]^[9].

§ 03

Operations

To merge two non-empty heaps, compare their roots. The smaller root becomes the root of the result; its left subtree is kept, and its right subtree is merged recursively with the other heap. On the way back, the helper make puts the child of larger rank on the left and sets the rank. Each recursive step moves one node down the right spine of one of the two heaps, so merging heaps of $n_{1}$ and $n_{2}$ elements takes at most $r_{1} + r_{2} = O (lo g n_{1} + lo g n_{2})$ steps^[3].

A leftist heap in OCaml.

(* A leftist heap: a heap-ordered binary tree in which every node's left
   child has rank at least that of its right child. The rank of a tree is
   the length of its right spine. *)
type 'a heap = E | T of int * 'a * 'a heap * 'a heap
 
let rank = function E -> 0 | T (r, _, _, _) -> r
 
(* Build a node, putting the child of larger rank on the left. *)
let make x a b =
  if rank a >= rank b then T (rank b + 1, x, a, b) else T (rank a + 1, x, b, a)
 
(* Merge walks down the two right spines, like merging sorted lists. *)
let rec merge h1 h2 =
  match h1, h2 with
  | E, h | h, E -> h
  | T (_, x, a1, b1), T (_, y, a2, b2) ->
    if x <= y then make x a1 (merge b1 h2) else make y a2 (merge h1 b2)
 
let singleton x = T (1, x, E, E)
let insert x h = merge (singleton x) h
let find_min = function E -> None | T (_, x, _, _) -> Some x
let delete_min = function E -> E | T (_, _, a, b) -> merge a b
 
(* Build a heap from a list in linear time by merging in pairs. *)
let of_list xs =
  let rec pass acc = function
    | a :: b :: rest -> pass (merge a b :: acc) rest
    | [h] -> h :: acc
    | [] -> acc
  in
  let rec go = function [] -> E | [h] -> h | hs -> go (pass [] hs) in
  go (List.map singleton xs)
 
let rec to_sorted_list h =
  match find_min h with None -> [] | Some x -> x :: to_sorted_list (delete_min h)

Insertion is merging with a single node, so it takes $O (lo g n)$ time, and delete_min merges the two children of the root in the same time. Building a heap by repeated insertion takes $O (n lo g n)$ ; merging the $n$ singletons in pairs, then the results in pairs, and so on, takes $O (n)$ because the $n / 2^{i}$ merges of round $i$ each cost $O (i)$ ^[3].

Merging two small heaps, and checking that the originals survive.

open Leftist
 
let rec show indent = function
  | E -> ()
  | T (r, x, a, b) ->
    Printf.printf "%s%d  (rank %d)\n" indent x r;
    show (indent ^ "  ") a; show (indent ^ "  ") b

Running it. Children are listed below their parent, left first.

h1:
  4  (rank 2)
    9  (rank 1)
    5  (rank 1)
      7  (rank 1)
h2:
  1  (rank 1)
    3  (rank 1)
      8  (rank 1)
merge h1 h2:
  1  (rank 2)
    4  (rank 2)
      9  (rank 1)
      5  (rank 1)
        7  (rank 1)
    3  (rank 1)
      8  (rank 1)
sorted: 1 3 4 5 7 8 9
h1 is unchanged: 4 5 7 9

Here the merge allocated a single node, the new root 1. Merging h1 with the empty right child of 1 returned h1 itself, and make then swapped the children because h1 has the larger rank. In general a merge allocates one node per step along the right spines and shares every other node with its arguments, which remain valid. This is what makes the structure persistent at no extra asymptotic cost^[3].

Rank and height for 100,000 elements inserted in random, ascending and descending order, and the cost of merging two large heaps.

open Leftist
 
let rec size = function E -> 0 | T (_, _, a, b) -> 1 + size a + size b
let rec height = function E -> 0 | T (_, _, a, b) -> 1 + max (height a) (height b)
 
(* Merge again, counting the recursive steps. *)
let steps = ref 0
let rec merge_counted h1 h2 =
  incr steps;
  match h1, h2 with
  | E, h | h, E -> h
  | T (_, x, a1, b1), T (_, y, a2, b2) ->
    if x <= y then make x a1 (merge_counted b1 h2) else make y a2 (merge_counted h1 b2)

Running it.

random     size 100000  rank 11  height 31
ascending  size 100000  rank 16  height 17
descending size 100000  rank 1  height 100000
log2(n + 1) = 16.61
merging two heaps of 100000: 21 steps, result rank 12
heap sort of the random input sorted: true

Ascending insertion reaches the bound exactly: $⌊ lo g_{2} 100001 ⌋ = 16$ . Descending insertion puts each new, smaller element at the root with the old heap as its left child, which gives a path of height 100,000 with rank 1; every operation on it is still cheap, because operations only follow right spines. Merging two heaps of 100,000 elements took 21 steps.

§ 04

Comparison with other heaps

The array-based binary heap of heapsort has the same $O (lo g n)$ insertion and deletion of the minimum and better constant factors, but merging two binary heaps requires rebuilding one of them, in $O (n)$ time^[10]. Later designs have improved on leftist heaps in different directions:

Binomial queues also merge in $O (lo g n)$ and insert in amortized constant time^[8]. Skew heaps drop the rank and swap the children at every step of a merge unconditionally; this gives $O (lo g n)$ amortized time with less bookkeeping, but amortization breaks down when old versions are reused, so skew heaps are not efficiently persistent^[4]. Weight-biased leftist trees use the size of a subtree instead of its rank; since sizes are known before the recursive call returns, merging can be done top-down in a single pass^[5]. Fibonacci heaps add constant amortized time for decreasing a key, which speeds up Dijkstra's and Prim's algorithms^[6], and Brodal and Okasaki gave a purely functional priority queue with worst-case constant-time insertion and merging^[7].

§ 05

History

Clark Allan Crane introduced the structure in his Stanford thesis of 1972 as a way to represent priority queues as balanced binary trees that support merging^[1]. Knuth presented it in the third volume of The Art of Computer Programming in 1973 under the name leftist trees^[2], and Tarjan's Data Structures and Network Algorithms of 1983 used leftist heaps as its basic meldable heap^[9]. Sleator and Tarjan's skew heaps were introduced in 1986 as a self-adjusting analogue^[4]. Okasaki's Purely Functional Data Structures of 1998 made leftist heaps the first example of a functional data structure with efficient persistent operations, and the pairwise construction in linear time is one of its exercises^[3].