我是否应该在列表中实现PriorityQueue ( OCaml )？

Question

我知道priorityQueue在Array上是完美的，因为它的本质已经到位。

应该在OCaml?中实现列表上的PriorityQueue (堆)吗？

如果我在List上这样做，那么我必须删除in-place，并想一种方法every time在每一步中创建一个新的列表。所以我想知道这是否值得。

事实上，我对此有更深层次的思考。

因此，许多fundamental算法/数据结构都是从in-place中发明出来的(我使用invented，因为我知道许多就地的算法/数据结构可以转换为not-in-place)。

但是，FL不推荐mutable。我的另一个问题是，如何在in-place / mutable immutable**和in OCaml之间进行选择，在** list 和 array**?**之间进行选择。

例如，在上面的priorityqueue案例中，如果我被要求用OCaml编写一个priorityqueue，我应该更喜欢array，因为它更自然、更容易，还是应该为了不可变而选择list？

Answer 1

使用不变的数据在模块化和可靠性方面提供了额外的好处。本质上，数据不可能通过其他模块的修改而损坏。模块不再需要担心其他模块，谁“拥有”数据。直到你不需要再做下去，你才会意识到这是多么的繁重。另一个意想不到的好处是，对代码的行为进行推理变得更加容易，因为它的作用就像一个数学函数。我在实践中经历了这两种情况，这使我成为了FP的信徒。成本通常是令人惊讶的适度，要么是一个较小的恒定因素，要么是额外的原木。

不变数据的另一个优点是持久化，即无需额外努力就能够维护数据的历史状态。(在不变的环境中实现撤销操作很有趣。)

尽管如此，我有时确实使用可变数据，因为它可以更快。

作为元注释，我建议您在OCaml中只使用不可变的数据。这是一个非常有趣的谜题，最初，如果没有其他。经过一些直接的经验，您将能够判断在特定情况下的权衡是什么。因此，我建议您尝试实现一个不变的优先级队列(或者阅读其他人是如何做到的)。

Answer 2

电池在这里有一个高效的功能堆：http://ocaml-batteries-team.github.com/batteries-included/hdoc2/BatHeap.html，find_min是O(1)，所有其他堆操作都是log(n)。

我相信实现是一个标准的二项堆，正如Okasaki所描述的那样。看看这里：https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batHeap.ml

但是，如果您仍然坚持使用具有破坏性操作的堆，那么我认为核心有一个从.NET中删除的实现，您必须仔细检查一下。

更重要的是，我同意Jeffrey的观点，并建议您首先使用功能数据结构，并且只在绝对必要时使用命令式数据结构。我相信这是以前向您建议过的，但是这类信息的最佳来源是Okasaki的纯功能数据结构书籍。我不能推荐它足够高。

Answer 3

二进制堆(您可能正在考虑的优先级队列的实现)通常是在动态数组(在某些语言中称为“向量”)上实现的，即您可以向其中添加元素或从其中删除元素。array不适合，因为它是固定大小的；创建它时，它的大小是固定的。您可以首先在array之上实现一个动态数组结构，然后在此基础上实现二进制堆(如果需要的话)。

优先级队列的另一种选择是使用自平衡二进制搜索树；OCaml标准目录已经有几个使用自平衡二进制搜索树- Set和Map的数据结构，它们被实现为不可变的功能性数据结构。自平衡二进制搜索树为大多数操作提供了与二进制堆相同的时间复杂度(移除最小元素和添加元素；这两个结构都是O(log ))。对于实现min元素的峰值化(二进制堆为O(1)；对于树为O(log ))，效率较低，但通常它本身并不使用。使用Set的一个问题是它不允许重复元素；理想情况下，您需要一个"multiset"，但是OCaml在标准库中没有一个；如果您不关心重复的元素，那么这不是一个问题。

我不建议为此使用list。