ts00ey

okasaki's pairing heap

the first time i heard of a pairing heap was when a friend whipped one out of thin air for an advent of code problem. pairing heaps are very performant in practice.

how i think of pairing heaps is they store a value (the minimum), and a list of other heaps. the condition that needs to hold is that the value is atleast as small (<= relationship) as the smallest value in all the other heaps (the ones in the list).

to merge two heaps together, to maintain the invariant (<= relationship). creating a new heap out of two, take the heap who's values is larger of the two and add it to the list of the heap who's value is smaller.

if we delete the minimum element from a heap, to maintain the invariant we just need to merge all the children heaps (the ones in the list) into a heap.

module Heap = struct
  type t =
    | Empty
    | Node of int * t list
  [@@deriving sexp]

  let empty t =
    match t with
    | Empty -> true
    | _ -> false
  ;;

  let merge t t' =
    match t, t' with
    | Empty, _ -> t'
    | _, Empty -> t
    | Node (x, lst), Node (x', lst') ->
      if x <= x' then Node (x, List.cons t' lst) else Node (x', List.cons t lst')
  ;;

  let insert x t = merge (Node (x, [])) t

  let rec merge_pairs lst =
    match lst with
    | [] -> Empty
    | [ x ] -> x
    | x :: y :: ys -> merge (merge x y) (merge_pairs ys)
  ;;

  let find_min t =
    match t with
    | Empty -> failwith "heap is empty, there is no minimum element"
    | Node (x, _) -> x
  ;;

  let delete_min t =
    match t with
    | Empty -> failwith "heap is empty, there is no minimum element to delete"
    | Node (_, lst) -> merge_pairs lst
  ;;
end