fork download 
  1. exception Empty
  2.  
  3. module type ORDERED = sig
  4.     type t
  5.  
  6.     val eq : t -> t -> bool
  7.     val lt : t -> t -> bool
  8.     val leq : t -> t -> bool
  9. end
  10.  
  11. module type HEAP = sig
  12.     module Elem : ORDERED
  13.  
  14.     type heap
  15.  
  16.     val empty : heap
  17.     val is_empty : heap -> bool
  18.  
  19.     val insert : Elem.t -> heap -> heap
  20.     val merge : heap -> heap -> heap
  21.  
  22.     val find_min : heap -> Elem.t
  23.     val delete_min : heap -> heap
  24. end
  25.  
  26. module SplayHeap (Element : ORDERED) : (HEAP with module Elem = Element) =
  27. struct
  28.   module Elem = Element
  29.  
  30.   type heap = E | T of heap * Elem.t * heap
  31.  
  32.   let empty = E
  33.   let is_empty h = h = E
  34.  
  35.   let partition pivot E = (E,E)
  36.   let partition pivot t as (T a x b) =
  37.       if x <= pivot then
  38.           case b of
  39.             E -> (t,E)
  40.             T b' y b'' ->
  41.                 if y <= pivot then
  42.                     let (small,big) = partition pivot b''
  43.                     in (T (T a x b) y small, big)
  44.                 else
  45.                     let (small,big) = partition pivot b'
  46.                     in (T a x small, T big y b'')
  47.       else
  48.           case a of
  49.             E -> (E,t)
  50.             T a' y a'' ->
  51.                 if y <= pivot then
  52.                     let (small,big) = partition pivot a''
  53.                     in (T a' y small, T big x b)
  54.                 else
  55.                     let (small, big) = partition pivot a'
  56.                     in (small, T big y (T a'' x b)
  57.  
  58.  
  59. end
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
File "prog.ml", line 36, characters 24-26:
Syntax error
stdout 
Standard output is empty
https://ideone.com/35J7lK
language:
OCaml (ocamlopt 4.05.0)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!