Ocaml Skew Heap

This directory contains two implementations of a Skew Heap, one that uses a built-in comparison operator, and another that allows you to specify your own comparison function similar to Haskell type classes.

The basic implementation of the Skew Heap in Ocaml is in skewheap_basic.ml. The data type and the merge (union) function are defined this way:

type skew_heap = Empty | SkewHeap of int * skew_heap * skew_heap

let rec skew_union h1 h2 =
  match h1, h2 with
  | SkewHeap (v1, l1, r1), SkewHeap (v2, l2, r2) ->
     if v1 <= v2 then
       SkewHeap (v1, (skew_union h2 r1), l1)
     else
       SkewHeap (v2, (skew_union h1 r2), l2)
  | Empty, h -> h
  | h, Empty -> h

You can compile the file with:

ocamlc skewheap_basic.ml

Here is an example session that displays an example heap and converts it to a list:

$ ocaml skewheap_basic.cmo
        OCaml version 4.13.1

Findlib has been successfully loaded. Additional directives:
  #require "package";;      to load a package
  #list;;                   to list the available packages
  #camlp4o;;                to load camlp4 (standard syntax)
  #camlp4r;;                to load camlp4 (revised syntax)
  #predicates "p,q,...";;   to set these predicates
  Topfind.reset();;         to force that packages will be reloaded
  #thread;;                 to enable threads

/home/mark/.opam/4.13.1/lib/ocaml/threads: added to search path
/home/mark/.opam/4.13.1/lib/ocaml/unix.cma: loaded
/home/mark/.opam/4.13.1/lib/ocaml/threads/threads.cma: loaded
# open Skewheap_basic;;
# foo_heap;;
- : Skewheap_basic.skew_heap =
SkewHeap (1,
 SkewHeap (2, SkewHeap (6, SkewHeap (10, Empty, Empty), Empty),
  SkewHeap (4, SkewHeap (8, Empty, Empty), Empty)),
 SkewHeap (3, SkewHeap (5, SkewHeap (9, Empty, Empty), Empty),
  SkewHeap (7, Empty, Empty)))
# to_list foo_heap;;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
# 

The basic implementation relies on a built-in comparison operator, but for custom data structures, you need to be able to specify a comparison function. You can define a module for a type and a comparison function this way:

module type Comparable = sig
    type t
    val compare : t -> t -> int
end

Then, you can define a module that takes the Comparable module as a parameter. Here is the module heading and the data type. Notice that Item.t is the type contained in the Comparable module:

module Make_skew_heap(Item : Comparable) = struct
  type skew_heap = Empty | SkewHeap of Item.t * skew_heap * skew_heap

Next, we implement skew_union using Item.compare to compare the items:

  let rec skew_union h1 h2 =
    match h1, h2 with
    | SkewHeap (v1, l1, r1), SkewHeap (v2, l2, r2) ->
       if Item.compare v1 v2 <= 0 then
         SkewHeap (v1, (skew_union h2 r1), l1)
       else
         SkewHeap (v2, (skew_union h1 r2), l2)
    | Empty, h -> h
    | h, Empty -> h

Here is a custom data type that contains a string and an int, as well as a function to compare them:

type thing = Thing of string * int

let compare_things t1 t2 =
    match t1,t2 with
    | Thing (_,v1), Thing (_,v2) -> Int.compare v1 v2

To create a Skew Heap to contain a thing, you use Make_skew_heap passing it a module defining the type t and the compare function. To show off the strength of Ocaml's modules (functors), we define two different heaps, one that sorts lowest to highest, the other that sorts highest to lowest:

module Thing_skewheap_smallest =
    Skewheap.Make_skew_heap(struct
        type t = thing
        let compare = compare_things
    end)

module Thing_skewheap_biggest =
    Skewheap.Make_skew_heap(struct
        type t = thing
        let compare v1 v2 = compare_things v2 v1
    end)

Finally, we create two heaps from lists, one sorted low-to-high, the other sorted high-to-load:

let stooge_heap_smallest = Thing_skewheap_smallest.from_list [
    Thing ("Curly",30); Thing ("Moe",100); Thing ("Joe",5);
    Thing ("Curly Joe",15); Thing ("Shemp",50); Thing ("Larry",85)]

let stooge_heap_biggest = Thing_skewheap_biggest.from_list [
    Thing ("Curly",30); Thing ("Moe",100); Thing ("Joe",5);
    Thing ("Curly Joe",15); Thing ("Shemp",50); Thing ("Larry",85)]

To compile these files, do:

ocamlc skewheap.ml skewheap_things.ml

Here is an example session that prints each example heap and converts it to a list:

$ ocaml skewheap.cmo skewheap_thing.cmo
        OCaml version 4.13.1

Findlib has been successfully loaded. Additional directives:
  #require "package";;      to load a package
  #list;;                   to list the available packages
  #camlp4o;;                to load camlp4 (standard syntax)
  #camlp4r;;                to load camlp4 (revised syntax)
  #predicates "p,q,...";;   to set these predicates
  Topfind.reset();;         to force that packages will be reloaded
  #thread;;                 to enable threads

/home/mark/.opam/4.13.1/lib/ocaml/threads: added to search path
/home/mark/.opam/4.13.1/lib/ocaml/unix.cma: loaded
/home/mark/.opam/4.13.1/lib/ocaml/threads/threads.cma: loaded
# open Skewheap_thing;;
# stooge_heap_smallest;;
- : Skewheap_thing.Thing_skewheap_smallest.skew_heap =
Skewheap_thing.Thing_skewheap_smallest.SkewHeap (Thing ("Joe", 5),
 Skewheap_thing.Thing_skewheap_smallest.SkewHeap (Thing ("Curly Joe", 15),
  Skewheap_thing.Thing_skewheap_smallest.SkewHeap (Thing ("Larry", 85),
   Skewheap_thing.Thing_skewheap_smallest.Empty,
   Skewheap_thing.Thing_skewheap_smallest.Empty),
  Skewheap_thing.Thing_skewheap_smallest.Empty),
 Skewheap_thing.Thing_skewheap_smallest.SkewHeap (Thing ("Curly", 30),
  Skewheap_thing.Thing_skewheap_smallest.SkewHeap (Thing ("Shemp", 50),
   Skewheap_thing.Thing_skewheap_smallest.Empty,
   Skewheap_thing.Thing_skewheap_smallest.Empty),
  Skewheap_thing.Thing_skewheap_smallest.SkewHeap (Thing ("Moe", 100),
   Skewheap_thing.Thing_skewheap_smallest.Empty,
   Skewheap_thing.Thing_skewheap_smallest.Empty)))
# Thing_skewheap_smallest.to_list stooge_heap_smallest;;
- : Skewheap_thing.thing list =
[Thing ("Joe", 5); Thing ("Curly Joe", 15); Thing ("Curly", 30);
 Thing ("Shemp", 50); Thing ("Larry", 85); Thing ("Moe", 100)]
# stooge_heap_biggest;;
- : Skewheap_thing.Thing_skewheap_biggest.skew_heap =
Skewheap_thing.Thing_skewheap_biggest.SkewHeap (Thing ("Moe", 100),
 Skewheap_thing.Thing_skewheap_biggest.SkewHeap (Thing ("Larry", 85),
  Skewheap_thing.Thing_skewheap_biggest.SkewHeap (Thing ("Curly", 30),
   Skewheap_thing.Thing_skewheap_biggest.SkewHeap (Thing ("Curly Joe", 15),
    Skewheap_thing.Thing_skewheap_biggest.Empty,
    Skewheap_thing.Thing_skewheap_biggest.Empty),
   Skewheap_thing.Thing_skewheap_biggest.Empty),
  Skewheap_thing.Thing_skewheap_biggest.Empty),
 Skewheap_thing.Thing_skewheap_biggest.SkewHeap (Thing ("Shemp", 50),
  Skewheap_thing.Thing_skewheap_biggest.SkewHeap (Thing ("Joe", 5),
   Skewheap_thing.Thing_skewheap_biggest.Empty,
   Skewheap_thing.Thing_skewheap_biggest.Empty),
  Skewheap_thing.Thing_skewheap_biggest.Empty))
# Thing_skewheap_biggest.to_list stooge_heap_biggest;;
- : Skewheap_thing.thing list =
[Thing ("Moe", 100); Thing ("Larry", 85); Thing ("Shemp", 50);
 Thing ("Curly", 30); Thing ("Curly Joe", 15); Thing ("Joe", 5)]
#