纯功能语言中的高效堆栈 [英] Efficient heaps in purely functional languages

问题描述

作为Haskell的练习，我试图实现heapsort。堆通常以命令式语言实现为一个数组，但这在纯功能语言中会非常低效。所以我研究过二进制堆，但到目前为止我发现的一切都是从一个强制性的观点来描述它们，并且所提出的算法很难转化为功能设置。如何有效地实现一个纯粹的函数式语言，如Haskell堆？

编辑：通过高效率我的意思是它应该仍然在O n * log n），但它不必击败C程序。另外，我想使用纯粹的函数式编程。在Haskell中做什么还有什么意义？

解决方案

在Okasaki的附录中有许多Haskell堆实现 纯粹功能性数据结构 。 （源代码可以在链接下载，本书非常值得一读。）它们本身都不是二进制堆，但是leftist堆非常相似。它有O（log n）插入，删除和合并操作。还有更复杂的数据结构，如倾斜堆，二项式堆砌，以及 splay heaps 有更好的表现。

As an exercise in Haskell, I'm trying to implement heapsort. The heap is usually implemented as an array in imperative languages, but this would be hugely inefficient in purely functional languages. So I've looked at binary heaps, but everything I found so far describes them from an imperative viewpoint and the algorithms presented are hard to translate to a functional setting. How to efficiently implement a heap in a purely functional language such as Haskell?

Edit: By efficient I mean it should still be in O(n*log n), but it doesn't have to beat a C program. Also, I'd like to use purely functional programming. What else would be the point of doing it in Haskell?

解决方案

There are a number of Haskell heap implementations in an appendix to Okasaki's Purely Functional Data Structures. (The source code can be downloaded at the link. The book itself is well worth reading.) None of them are binary heaps, per se, but the "leftist" heap is very similar. It has O(log n) insertion, removal, and merge operations. There are also more complicated data structures like skew heaps, binomial heaps, and splay heaps which have better performance.

这篇关于纯功能语言中的高效堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！