heap.ml

(* Polymorphic pairing heap. This should really be a functor such
   that it can be made min/max/whatever *)
type 'a heap = Empty | Heap of 'a * ('a heap) list

let empty = Empty

let is_empty h = match h with 
    Empty -> true
  | _ -> false

(* meld's > should be functorized *)
let meld a b = match (a, b) with
    Empty, b -> b
  | a, Empty -> a
  | Heap (a, al), Heap (b, bl) -> if a < b then
                                       Heap (a, (Heap (b, bl)) :: al)
                                  else
                                       Heap (b, (Heap (a, al)) :: bl)

let meld_all hs = match hs with
    [] -> Empty
  | h :: [] -> h
  | h :: hs -> List.fold_left meld h hs

let insert e h = meld (Heap (e, [])) h

let head h = match h with
    Empty -> failwith "foo"
  | Heap (e, _) -> e

let tail h = match h with
    Empty -> failwith "foo"
  | Heap (e, []) -> Empty
  | Heap (e, h :: []) -> h
  | Heap (e, hs) -> meld_all hs