(* This code extends 'mini_prelude'. *)

type ('a) heap = 
    Tree of ('a) heap * 'a * ('a) heap 
  | Empty ;;

let empty = Empty ;;

let is_empty = 
  (fun v4 -> 
    (match v4 with 
        Empty -> true 
      | (Tree (v3, v2, v1)) -> false)) ;;

let rec partition v22 = 
  (fun v23 -> 
    (fun v24 -> 
      (fun v25 -> 
        (match v25 with 
            Empty -> (Pair (Empty, Empty)) 
          | (Tree (v21, v20, v19)) -> 
              (if ((v23 (v22 v20)) (v22 v24)) 
              then 
                (match v19 with 
                    Empty -> (Pair ((Tree (v21, v20, v19)), Empty)) 
                  | (Tree (v9, v8, v7)) -> 
                      (if ((v23 (v22 v8)) (v22 v24)) 
                      then 
                        (let v3 = ((((partition v22) v23) v24) v7) 
                        in 
                          (match v3 with 
                              (Pair (v2, v1)) -> (Pair ((Tree ((Tree (v21, v20, v9)), v8, v2)), v1)))) 
                      else 
                        (let v6 = ((((partition v22) v23) v24) v9) 
                        in 
                          (match v6 with 
                              (Pair (v5, v4)) -> (Pair ((Tree (v21, v20, v5)), (Tree (v4, v8, v7)))))))) 
              else 
                (match v21 with 
                    Empty -> (Pair (Empty, (Tree (v21, v20, v19)))) 
                  | (Tree (v18, v17, v16)) -> 
                      (if ((v23 (v22 v17)) (v22 v24)) 
                      then 
                        (let v12 = ((((partition v22) v23) v24) v16) 
                        in 
                          (match v12 with 
                              (Pair (v11, v10)) -> (Pair ((Tree (v18, v17, v11)), (Tree (v10, v20, v19)))))) 
                      else 
                        (let v15 = ((((partition v22) v23) v24) v18) 
                        in 
                          (match v15 with 
                              (Pair (v14, v13)) -> (Pair (v14, (Tree (v13, v17, (Tree (v16, v20, v19))))))))))))))) ;;

let insert = 
  (fun v4 -> 
    (fun v5 -> 
      (fun v7 -> 
        (fun v6 -> 
          (let v3 = ((((partition v4) v5) v7) v6) 
          in 
            (match v3 with 
                (Pair (v2, v1)) -> (Tree (v2, v7, v1)))))))) ;;

let rec merge v8 = 
  (fun v9 -> 
    (fun v10 -> 
      (fun v7 -> 
        (match v10 with 
            Empty -> v7 
          | (Tree (v6, v5, v4)) -> 
              (let v3 = ((((partition v8) v9) v5) v7) 
              in 
                (match v3 with 
                    (Pair (v2, v1)) -> (Tree (((((merge v8) v9) v2) v6), v5, ((((merge v8) v9) v1) v4))))))))) ;;

let rec find_min x = 
  (match x with 
      Empty -> (raise (Match_failure (string_of_bool true, 0, 0))) 
    | (Tree (v6, v5, v4)) -> 
        (match v6 with 
            Empty -> v5 
          | (Tree (v3, v2, v1)) -> (find_min (Tree (v3, v2, v1))))) ;;

let rec delete_min x = 
  (match x with 
      Empty -> (raise (Match_failure (string_of_bool true, 0, 0))) 
    | (Tree (v9, v8, v7)) -> 
        (match v9 with 
            Empty -> v7 
          | (Tree (v6, v5, v4)) -> 
              (match v6 with 
                  Empty -> (Tree (v4, v8, v7)) 
                | (Tree (v3, v2, v1)) -> (Tree ((delete_min (Tree (v3, v2, v1))), v5, (Tree (v4, v8, v7))))))) ;;