Function for priority queue in ocaml

Question

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

I checked this " http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.Make.html " but there is no example of how to use these commands anywhere.

Answer 1

OCaml batteries contain a polymorphic priority queue in a module called BatHeap . You can use it by simply adding items to an empty heap, etc.

Jane Stree Core has a priority priority queue in a module named Heap .

Update:

A bunch of Jane Stree Nuclei is really a fantasy. One way to describe this is through two heap interfaces. The first interface is a set of ordered values, whose smallest element can be located in constant time and deleted during the log. The second interface considers the heap as a collection of containers ("heaps of elements") with ordered values ​​in them. If you are ready to handle these containers explicitly, some of the heap operations can be completed faster.

Here is a very simple example that uses a bunch (first interface) to sort the list:

let heapsort l = let heap = Core.Std.Heap.create compare in List.iter (fun x -> ignore (Core.Std.Heap.push heap x)) l; let rec extract () = match Core.Std.Heap.pop heap with | None -> [] | Some x -> x :: extract () in extract () 

(This code is somewhat artificial, it just shows how to put the values ​​in a heap and return them.)

Here is an example of running this code (in OCaml toplevel with Core support):

 # #use "sort.ml";; val heapsort : 'a list -> 'a list = <fun> # heapsort [3;1;4;1;5;9];; - : int list = [1; 1; 3; 4; 5; 9] # 

Answer 2

The OCaml Modular Management System chapter begins with a sample code that implements the priority queue. This is my implementation of priority queues, and since the entire implementation corresponds to 25 lines, it is easy to use and understand.

Answer 3

Here is a slightly larger tutorial for kernel 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)) 

Feel free to use Core. This will make your OCaml much nicer. More questions are always welcome.