(* structure de tas *)

type heap = Null | Fork of int * heap * heap

let empty = Null

let rec merge = function
  | Null, a | a, Null -> 
      a
  | Fork (xa, a, b), (Fork (xb, _, _) as c) when xa <= xb -> 
      Fork (xa, b, merge (a, c))
  | Fork (xa, _, _) as c, Fork (xb, a, b) ->
      Fork (xb, b, merge (a, c))
        
let add x h = merge (Fork (x, Null, Null), h)

exception EmptyHeap

let extract_min = function
  | Null -> raise EmptyHeap
  | Fork (x, a, b) -> x, merge (a, b)

(* application : heapsort *)

let rec heap_of_list = function
  | [] -> empty
  | x :: r -> add x (heap_of_list r)

let rec list_of_heap h =
  if h = Null then
    []
  else
    let x, h = extract_min h in x :: list_of_heap h

let heapsort l = list_of_heap (heap_of_list l)

This document was generated using caml2html