open Okasaki
open OrderedSig
open HeapSig

module PairingHeap (Element : Ordered) : Heap =
struct
  module Element = Element

  type heaps = Empty | Node of Element.t * heaps list
  type heap = heaps

  let empty = Empty

  let is_empty = function
     | Empty -> true
     | _ -> false

  let merge h1 h2 = 
     match h1, h2 with
     | _, Empty -> h1
     | Empty, _ -> h2
     | Node (x, hs1), Node (y, hs2) ->
         if Element.leq x y 
            then Node (x, h2 :: hs1)
            else Node (y, h1 :: hs2)

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

  let rec merge_pairs = function
     | [] -> Empty
     | [h] -> h
     | h1::h2::hs -> merge (merge h1 h2) (merge_pairs hs)

  let find_min = function 
     | Empty -> raise EmptyStructure 
     | Node (x, _) -> x
  
  let delete_min = function 
     | Empty -> raise EmptyStructure 
     | Node (x, hs) -> merge_pairs hs

end