Data Structures in ReasonML: #7 Heap

Heap.re

/* Heap */
exception Not_Found;

module type Ord = {type t; let compare: (t, t) => int;};

module Integer = {
  type t = int;
  let compare = (a, b) => a - b;
};

module type Heap = {
  type t;
  type height = int;
  type heap =
    | Empty
    | Node(height, heap, t, heap);
  let empty: heap;
  let isEmpty: heap => bool;
  let insert: (t, heap) => heap;
  let getHeight: heap => int;
  let merge: (heap, heap) => heap;
  let getMin: heap => t;
  let deleteMin: heap => heap;
};

exception Empty;

module MakeHeap = (Elem: Ord) : (Heap with type t = Elem.t) => {
  type t = Elem.t;
  type height = int;
  type heap =
    | Empty
    | Node(height, heap, t, heap);
  let empty = Empty;
  let isEmpty = heap => heap === Empty;
  let getHeight = heap =>
    switch (heap) {
    | Empty => 0
    | Node(height, _, _, _) => height
    };
  let makeT = (value, left, right) =>
    if (getHeight(left) >= getHeight(right)) {
      Node(getHeight(right) + 1, left, value, right);
    } else {
      Node(getHeight(left) + 1, right, value, left);
    };
  let rec merge = (heap1, heap2) =>
    switch (heap1, heap2) {
    | (heap1, Empty) => heap1
    | (Empty, heap2) => heap2
    | (Node(_, ll, lv, lr), Node(_, rl, rv, rr)) =>
      if (Elem.compare(lv, rv) < 0) {
        makeT(lv, ll, merge(lr, heap2));
      } else {
        makeT(rv, rl, merge(rr, heap1));
      }
    };
  let insert = (value, heap) => merge(Node(1, Empty, value, Empty), heap);
  let getMin = heap =>
    switch (heap) {
    | Empty => raise(Not_Found)
    | Node(_, _, value, _) => value
    };
  let deleteMin = heap =>
    switch (heap) {
    | Empty => raise(Not_Found)
    | Node(_, left, _, right) => merge(left, right)
    };
};

let run = () => {
  module LeftistHeap = MakeHeap(Integer);
  let t = LeftistHeap.empty;
  Js.log2("is empty?", LeftistHeap.isEmpty(t)); /* // => true */
  let t = LeftistHeap.insert(10, t);
  Js.log2("is empty?", LeftistHeap.isEmpty(t)); /* // => false */
  let t = LeftistHeap.insert(12, t);
  Js.log2("get min: ", LeftistHeap.getMin(t)); /* // => 10 */
  let t = LeftistHeap.insert(7, t);
  let t = LeftistHeap.insert(17, t);
  Js.log2("get min: ", LeftistHeap.getMin(t)); /* // => 7 */
  let t = LeftistHeap.insert(2, t);
  let t = LeftistHeap.insert(5, t);
  let t = LeftistHeap.insert(8, t);
  Js.log2("get min: ", LeftistHeap.getMin(t)); /* // => 2 */
  Js.log("remove min");
  let t = LeftistHeap.deleteMin(t);
  Js.log2("get min: ", LeftistHeap.getMin(t)); /* // => 5 */
};

run();