我知道这priorityQueue是完美的，Array因为它的性质已经到位。
我应该在 OCaml 中的列表上实现 PriorityQueue（堆）吗？
如果我这样做List，那么我必须删除这个in-place东西并想办法every time在每一步中创建一个新列表。所以我想知道是否值得。
其实，我对此有更深的思考。
因此，许多fundamental算法/数据结构是从发明的in-place（我使用invented是因为我知道许多就地可以转换为not-in-place）。
不过，FL不推荐mutable的东西。我的另一个问题是如何在 和 之间进行in-place / mutable选择immutable？或者在 OCaml 中，我什么时候应该在 和 之间进行list选择array？
例如，在上述priorityqueue情况下，如果我被要求priorityqueue在 OCaml 中编写 a，我应该更喜欢array它更自然、更容易，还是应该选择 list 以保持不变？
使用不可变数据在模块化和可靠性方面带来了惊人的好处。本质上，数据不可能通过其他模块的修改而损坏。模块不再需要担心其他模块，以及谁“拥有”数据。在您不再需要这样做之前，您不会意识到这是多么繁重。另一个意想不到的好处是推理代码的行为变得更加容易，因为它就像一个数学函数。我在实践中经历了这两种情况，这使我成为了 FP 的信徒。成本通常出人意料地适中，要么是一个很小的常数因子，要么可能是额外的log n。
不可变数据的另一个优点是持久性，即无需额外努力即可维护数据的历史状态的能力。（在不可变环境中实现撤消操作很有趣。）
也就是说，我有时确实使用可变数据，因为它可以更快。
作为元评论，我建议您花一些时间在 OCaml 中仅使用不可变数据。如果没有别的，它最初是一个非常有趣的谜题。在一些直接的经验之后，您将能够判断在特定情况下的权衡取舍所在。所以我建议你尝试实现一个不可变的优先级队列（或阅读其他人是如何做到的）。
电池在这里有一个有效的功能堆：http: //ocaml-batteries-team.github.com/batteries-included/hdoc2/BatHeap.html find_min 为 O(1) 并且所有其他堆操作都是 log(n)
我相信该实现是冈崎中描述的标准二项式堆。看看这里：https ://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batHeap.ml
但是，如果您仍然坚持使用破坏性操作的堆，那么我认为核心有一个从 .NET 中删除的实现。你得仔细看看。
更重要的是，我同意 Jeffrey 的观点，并建议您首先对函数式数据结构感到非常熟悉，并且仅在绝对必要时才使用命令式数据结构。我敢肯定，以前有人向您建议过，但此类信息的最佳来源是冈崎的纯函数数据结构书。我不能高度推荐它。
二进制堆（您可能正在考虑的优先级队列的实现）通常在动态数组（在某些语言中称为“向量”）上实现，即您可以向其中添加元素或从中删除元素的数组。array不适合，因为它是固定大小的；创建时它的大小是固定的。您可以首先在 之上实现一个动态数组结构array，然后在其之上实现二进制堆，如果您愿意的话。
优先级队列的另一个选择是使用自平衡二叉搜索树；OCaml 标准库已经有几个使用自平衡二叉搜索树的数据结构——Set并且Map，它们被实现为不可变的功能数据结构。自平衡二叉搜索树为大多数操作提供与二叉堆相同的时间复杂度（删除最小元素和添加元素；这两种结构的时间复杂度为 O(log n)）。使最小元素达到峰值的效率较低（二进制堆为 O(1)；树为 O(log n)），但它通常不单独使用。using 的一个问题Set是它不允许重复元素。理想情况下，您会想要一个“multiset”，但 OCaml 在标准库中没有；如果你不关心重复元素，
我不建议list为此使用。