Function for priority queue in ocaml

Question

Is there a library in ocaml with which I could make a priority queue and handle it?

I have checked this "http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.Make.html" but it does not have anywhere an example of how to use these commands.

Answer 1

Here's a slightly larger tutorial for Core's heap.

open Core.Std

(* A heap only expects a comparsion function on its elements. Use
  polymorphic compare if you just want something tham makes sense most
  of the time *)

let pq = Heap.create compare

let reverse_pq = Heap.create ~min_size:10 (Fn.flip compare)

(* The optional min size argument is there for optimization purposes. If you
   know that your heap will grow past a certain size you can allocate the array
   of that size in advance to save copying/resizing later on since the heap is
   array based *)

let () = 
  let random_list = List.init 10 ~f:(fun _ -> Random.int 10) in
  (* core wraps values inserted into the heap in the type 'el heap_el
    where 'el is the type of elements in your heap *)
  let heap_el = Heap.push pq (Random.int 10) in
  (* this gives you O(1) existence check in the heap: *)
  let x = Heap.heap_el_mem pq heap_el in (* true in O(1) *)
  let value_in_el = Heap.heap_el_get_el heap_el in
  (* now standard heap stuff, insert a list into a heap *)
  random_list |> List.iter ~f:(Fn.compose ignore (Heap.push pq));
  (* now drain the heap and get a list in sorted order, for reverse
  order you'd us reverse_pq *)
  let sorted_list = 
    let rec loop acc =
      match Heap.pop pq with
      | None -> acc
      | Some e -> loop (e::acc)
    in loop [] in
  printf "Sorted: %s\n" 
    (Sexp.to_string_hum (List.sexp_of_t Int.sexp_of_t sorted_list))

Don't hesitate to use Core. It will make your OCaml much more pleasant. More questions are always welcome.