纯function语言中的高效堆

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

编辑：效率我的意思是它应该仍然在O（N *日志），但它不必击败一个C程序。 另外，我想使用纯function编程。 在Haskell中做什么呢？

Answer 1

冈崎纯粹function数据结构附录中有许多Haskell堆实现。 （源代码可以在链接下载，本书非常值得一读。）本质上它们都不是二进制堆，但“左”堆非常相似。 它有O（log n）插入，删除和合并操作。 还有更复杂的数据结构，如倾斜堆 ， 二项堆 ，以及具有更好性能的散列堆 。

Answer 2

Jon Fairbairn早在1997年就向Haskell咖啡馆邮件列表发布了一个函数堆：

http://www.mail-archive.com/[e-mail]/msg01788.html

我重现下面，重新格式化，以适应这个空间。 我也稍微简化了merge_heap的代码。

我很惊讶treefold是不是在标准的前奏，因为它是如此有用。 从1992年10月我在“思考”中写到的版本 – 乔恩·费尔贝恩（Jon Fairbairn）

module Treefold where -- treefold (*) z [a,b,c,d,e,f] = (((a*b)*(c*d))*(e*f)) treefold f zero [] = zero treefold f zero [x] = x treefold f zero (a:b:l) = treefold f zero (fab : pairfold l) where pairfold (x:y:rest) = fxy : pairfold rest pairfold l = l -- here l will have fewer than 2 elements module Heapsort where import Treefold data Heap a = Nil | Node a [Heap a] heapify x = Node x [] heapsort :: Ord a => [a] -> [a] heapsort = flatten_heap . merge_heaps . map heapify where merge_heaps :: Ord a => [Heap a] -> Heap a merge_heaps = treefold merge_heap Nil flatten_heap Nil = [] flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps) merge_heap heap Nil = heap merge_heap node_a@(Node a heaps_a) node_b@(Node b heaps_b) | a < b = Node a (node_b: heaps_a) | otherwise = Node b (node_a: heaps_b) 

Answer 3

你也可以使用ST monad，它允许你编写命令式的代码，但安全地暴露一个纯粹的function接口。

Answer 4

作为Haskell的一个练习，我用ST Monad实现了一个必要的堆sorting。

 {-# LANGUAGE ScopedTypeVariables #-} import Control.Monad (forM, forM_) import Control.Monad.ST (ST, runST) import Data.Array.MArray (newListArray, readArray, writeArray) import Data.Array.ST (STArray) import Data.STRef (newSTRef, readSTRef, writeSTRef) heapSort :: forall a. Ord a => [a] -> [a] heapSort list = runST $ do let n = length list heap <- newListArray (1, n) list :: ST s (STArray s Int a) heapSizeRef <- newSTRef n let heapifyDown pos = do val <- readArray heap pos heapSize <- readSTRef heapSizeRef let children = filter (<= heapSize) [pos*2, pos*2+1] childrenVals <- forM children $ \i -> do childVal <- readArray heap i return (childVal, i) let (minChildVal, minChildIdx) = minimum childrenVals if null children || val < minChildVal then return () else do writeArray heap pos minChildVal writeArray heap minChildIdx val heapifyDown minChildIdx lastParent = n `div` 2 forM_ [lastParent,lastParent-1..1] heapifyDown forM [n,n-1..1] $ \i -> do top <- readArray heap 1 val <- readArray heap i writeArray heap 1 val writeSTRef heapSizeRef (i-1) heapifyDown 1 return top 

顺便说一句，我认为，如果它不是纯粹的function，那么在Haskell中这样做没有意义。 我认为我的玩具实现比用C ++在模板中实现的要好得多，将内容传递给内部函数。

Answer 5

这里是一个在Haskell中的Fibonacci堆：

https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/heap/other-heaps/src/FibonacciHeap.hs

这里是基于冈崎工作的其他一些k-ary堆的pdf文件。

downloads/liuxinyu95/AlgoXY/kheap-en.pdf

Answer 6

就像使用Haskell编写的高效Quicksortalgorithm一样，您需要使用monads（状态转换器）在原地进行操作。

Answer 7

我试图将标准二进制堆移植到function设置。 有一篇文章描述了这个想法： 标准二进制堆的function方法 。 文章中的所有源代码都在Scala中。 但它可能很容易移植到任何其他function语言。

Answer 8

Haskell中的数组并不像你想象的那样效率太低，但是Haskell中的典型做法可能是使用普通的数据types来实现这一点，比如：

 data Heap a = Empty | Heap a (Heap a) (Heap a) fromList :: Ord a => [a] -> Heap a toSortedList :: Ord a => Heap a -> [a] heapSort = toSortedList . fromList 

如果我正在解决这个问题，我可能会开始填充列表元素到一个数组中，使它更容易索引他们的堆创build。

 import Data.Array fromList xs = heapify 0 where size = length xs elems = listArray (0, size - 1) xs :: Array Int a heapify n = ... 

如果您使用的是二进制最大堆，则可能需要在移除元素时跟踪堆的大小，以便在O（log N）时间内find右下angular的元素。 您还可以看看其他types的堆，通常不使用数组实现，如二项堆和斐波那契堆。

关于数组性能的最后一点是：在Haskell中，使用静态数组和使用可变数组之间有一个折衷。 对于静态数组，当您更改元素时，必须创build新的数组副本。 使用可变数组时，垃圾收集器很难将不同世代的对象分开。 尝试使用STArray实现heapsort，看看你喜欢它。

Answer 9

这是一个包含ML版本的HeapSort的页面。 这是相当详细的，应该提供一个很好的起点。

http://flint.cs.yale.edu/cs428/coq/doc/Reference-Manual021.html