(* This file describes the signature of the module [LeftistHeap].
   That is, it describes the types and operations defined in this
   module. *)

(* For simplicity, we decide that the elements of a priority queue
   are integers. Smaller integers represent greater priority. *)

type element =
  int

(* The abstract type [heap] represents a priority queue. *)

type queue

(* The empty queue. *)

val empty: queue

(* Insertion. O(log n) *)

val insert: element -> queue -> queue

(* Merging. O(log n) *)

val merge: queue -> queue -> queue

(* Extraction of the minimum element. O(log n) *)

val extract: queue -> (element * queue) option