haskell - 如何实现纯函数式标准二进制堆(ocaml 或 haskell)？

Question

是否有纯函数式标准二进制堆的实现？我知道有很多有趣的堆，例如:二项式堆、左式堆，它们都有函数实现，只是想知道是否有一种方法可以实现标准二元堆，或者由于不可变类型，我们必须使用数组来实现它？谢谢!

Answer 1

您不需要数组来实现堆，您可以将其实现为树结构。

data Heap t = Node t (Heap t) (Heap t) | Nil

缺点是您最终会为每个堆操作重新分配 O(log N) 节点，并且您不会拥有基于命令式数组的实现的任何缓存局部性。对于这种结构，某些操作会很困难，但由于我不知道您想对堆做什么，所以无法为您指出更具体的方向。

我们拥有像手指树这样的特殊功能结构的原因是为了加速通常不在堆上执行的特定操作，例如检索最左边的叶节点。您可以在 Haskell 中使用您在命令式语言中学到的许多相同的数据结构，只需更改它们的更新方式即可。