Pairing heap

A pairing heap is a multiway tree in heap order: every node's element is no larger than its children's^[1]. All the work happens in delete_min. Merging two heaps makes the root with the larger element a child of the other, which is constant time, and insertion is merging with a one-element heap. Removing the root leaves a list of subtrees that must be combined into one, and the order in which they are merged is what makes the structure efficient.

(* A pairing heap: a heap-ordered tree with any number of children. *)
type 'a heap = Empty | T of 'a * 'a heap list
 
let merges = ref 0
 
let merge h1 h2 =
  match (h1, h2) with
  | Empty, h | h, Empty -> h
  | T (x, hs1), T (y, hs2) ->
      incr merges;
      if x <= y then T (x, h2 :: hs1) else T (y, h1 :: hs2)
 
let insert x h = merge (T (x, [])) h
let find_min = function Empty -> None | T (x, _) -> Some x
 
(* Two passes: merge the children in pairs from left to right, then merge
   the pairs from right to left. *)
let rec merge_pairs = function
  | [] -> Empty
  | [ h ] -> h
  | h1 :: h2 :: hs -> merge (merge h1 h2) (merge_pairs hs)
 
let delete_min = function Empty -> Empty | T (_, hs) -> merge_pairs hs

After the root is removed, merge_pairs merges the first two children, the next two, and so on, then merges these results from the last to the first^[1].

Fredman, Sedgewick, Sleator and Tarjan proved that with this two-pass rule delete_min takes $O(\log n)$ amortized time^[1]. Iacono later showed that insertion can be charged $O(1)$ amortized time while deletion stays logarithmic^[3]. The pairing in the first pass matters: merging the children one after another can leave a root with nearly as many children as before, and the next deletion repeats the work.

open Pairing
 
(* The naive alternative: merge the children one at a time. *)
let delete_min_naive = function Empty -> Empty | T (_, hs) -> List.fold_left merge Empty hs
 
let drain name delete_min h =
  merges := 0;
  let rec go h acc = match find_min h with None -> List.rev acc | Some x -> go (delete_min h) (x :: acc) in
  let out = go h [] in
  Printf.printf "%-10s sorted %b, %9d merges\n" name (out = List.sort compare out) !merges
 
let n = 10_000

two-pass   sorted true,    153290 merges
naive      sorted true,  16684322 merges
two-pass   sorted true,    153096 merges
naive      sorted true,  16764364 merges

The two-pass heap did about 15 merges per deletion, close to ${\log }_{2}10000\approx 13$. Merging the children one at a time did more than a hundred times as many.

Imperative pairing heaps also support decreasing the key of a node: cut the node's subtree from its parent and merge it with the root. Its exact cost is still open. Fredman proved a lower bound of $\Omega (\log \log n)$ amortized for pairing heaps and related structures, so they cannot match Fibonacci heaps' constant time^[4], and Pettie proved an upper bound of $O(2^{2\sqrt{\log \log n}})$^[5]. In experiments pairing heaps are usually faster than Fibonacci heaps all the same^[2].

As with other amortized structures, the bounds assume each version is used once. In a functional setting, repeatedly deleting from the same old version repeats the expensive pairing pass each time; Okasaki makes the structure persistent with lazy evaluation^[6].

Fredman, Sedgewick, Sleator and Tarjan introduced pairing heaps in 1986 as a simpler alternative to Fibonacci heaps, conjecturing that they had the same amortized bounds^[1]. Stasko and Vitter found them faster in experiments in 1987^[2]. Fredman disproved the conjecture for decrease-key in 1999^[4], and Iacono in 2000 and Pettie in 2005 tightened the remaining bounds^[3][5].

• Leftist heapA leftist heap is a priority queue represented as a heap-ordered binary tree in which, at every node, the right spine of the left child is at least as long as the right spine of the right child. The right spine of the whole tree then has at most log₂(n + 1) nodes, and two heaps can be merged in O(log n) time by merging their right spines like sorted lists. Insertion and deletion of the minimum are special cases of merging. Because merging copies only the right spines, leftist heaps are a standard persistent priority queue in functional languages.
• Skew binomial heapA skew binomial heap is a priority queue made of a list of heap-ordered trees whose sizes follow the skew binary number system, in which adding one never carries more than one digit. Insertion therefore takes constant time in the worst case, instead of the logarithmic worst case of an ordinary binomial heap, while merging, finding the minimum and deleting it take logarithmic time. Brodal and Okasaki used it as the base of a purely functional priority queue with optimal bounds.
• Splay treeA splay tree is a binary search tree that keeps no balance information and instead moves every node it accesses to the root, by a sequence of rotations called splaying. Single operations can take linear time, but any sequence of m operations on a tree of n nodes takes O((m + n) log n) time, so each operation is logarithmic amortized. Because recently used keys end up near the root, splay trees adapt to the access pattern.

1. [1]M. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan, “The pairing heap: a new form of self-adjusting heap”, Algorithmica 1 (1986).
2. [2]J. T. Stasko, J. S. Vitter, “Pairing heaps: experiments and analysis”, Communications of the ACM 30 (1987).
3. [3]J. Iacono, “Improved upper bounds for pairing heaps”, SWAT (2000).
4. [4]M. L. Fredman, “On the efficiency of pairing heaps and related data structures”, Journal of the ACM 46 (1999).
5. [5]S. Pettie, “Towards a final analysis of pairing heaps”, FOCS (2005).
6. [6]C. Okasaki, Purely Functional Data Structures, §5.5, Cambridge University Press (1998).

last updated 1 October 2026