OCaml中优先队列的函数

Question

有没有一个OCaml库可以创建优先队列并对其进行处理？

我查看了这个网址"http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.Make.html"，但它没有任何关于如何使用这些命令的示例。

- Hobowpen

Answer 1

这是一个更为详细的Core 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))

不要犹豫使用Core，它会让你的OCaml编程更加愉悦。如有更多问题，请随时咨询。

- rgrinberg

Answer 2

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 ()

（这段代码有些人为，只是展示如何将值放入堆中并将其取回。）

以下是运行此代码的示例（在带有Core支持的OCaml toplevel中）：

# #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]
# 

- Jeffrey Scofield

---

我已经检查过它们了，如果我知道如何使用它们，那将非常有用。我是OCaml的新手，我需要一个演示来弄清楚如何使用“create”。当我阅读val create: ?min_size:int -> ('el -> 'el -> int) -> 'el t create ?min_size cmp时，我可以理解“create”的作用，但不知道如何使用（我的意思是它接受什么操作数以及我该如何调用它）。 - Hobowpen

我正在安装Jane Street Core，但很遗憾在晚饭之前我无法为您提供示例。还有许多其他的Core用户可能会更快地提供帮助:-)。 - Jeffrey Scofield

谢谢你的帮助！唯一我不明白的是，当我读到这个 "val create : ?min_size:int -> ('el -> 'el -> int) -> 'el t create ?min_size cmp" 时，我怎么知道要写 Core.Std.Heap.create。是否有什么东西我可以阅读来更容易地理解这种事情？ - Hobowpen

Answer 3

OCaml手册中的章节模块系统以实现优先队列的代码示例开始。这是我首选的优先队列实现，由于整个实现仅有25行，因此易于使用和理解。

- gasche

---

谢谢您的回答。我想在这段代码中添加两个功能。一个是可以查找特定元素的功能，另一个是可以删除它的功能。我尝试实现它，但遇到了一些问题。 - Hobowpen

此链接已经失效。 - rgrinberg

感谢 @rgrinberg，我放了一个更持久的链接。 - gasche