有没有一个OCaml库可以创建优先队列并对其进行处理?
我查看了这个网址"http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.Make.html",但它没有任何关于如何使用这些命令的示例。
有没有一个OCaml库可以创建优先队列并对其进行处理?
我查看了这个网址"http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.Make.html",但它没有任何关于如何使用这些命令的示例。
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))
不要犹豫使用Core,它会让你的OCaml编程更加愉悦。如有更多问题,请随时咨询。
OCaml Batteries included在名为BatHeap的模块中提供了一个多态优先队列。您只需向空堆添加元素即可使用它。
Jane Stree Core在名为Heap的模块中提供了一个更高级的优先队列。
更新:
Jane Stree Core的Heap确实很漂亮。描述它的一种方式是,堆有两个接口。第一个接口将堆视为有序值的集合,其最小元素可以在常数时间内定位并在对数时间内删除。第二个接口将堆视为包含有序值的容器(“堆元素”)的集合。如果您愿意显式处理这些容器,则可以更快地执行一些堆操作。
这里是一个极其简单的示例,使用堆(第一个接口)对列表进行排序:
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 ()
# #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]
#
OCaml手册中的章节模块系统以实现优先队列的代码示例开始。这是我首选的优先队列实现,由于整个实现仅有25行,因此易于使用和理解。