ocaml 中是否有一个库,我可以使用它来创建优先级队列并处理它?
我已经检查了这个“http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.Make.html”
但它在任何地方都没有关于如何使用这些命令的示例。
最佳答案
这是一个稍微大一点的Core堆教程。
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))
不要犹豫,使用核心。它会让你的 OCaml 更加愉快。欢迎提出更多问题。
关于ocaml - ocaml中优先级队列的功能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17076875/