纯功能语言中的高效堆

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

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

来源

2009-05-31 Kim Stebel

Okasaki的Purely Functional Data Structures附录中有许多Haskell堆实现。（源代码可以在链接下载，本书非常值得一读。）本质上它们都不是二进制堆，但"leftist" heap非常相似。它有O（log n）插入，删除和合并操作。还有更复杂的数据结构，如skew heaps,binomial heaps和splay heaps，它们具有更好的性能。

来源

2009-05-31 21:53:54

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

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

来源

2009-05-31 19:59:30 JaredPar

就像在写在Haskell中高效快速排序算法，你需要使用单子（州变压器）做的东西在的地方。

来源

2009-05-31 20:20:35

-1：没有人能够在Haskell中写出高效的快速排序。 – 2010-05-23 16:34:42

这一个是非常有效的，https://gist.github.com/dmjio/3478bd19737e2011b750 @JonHarrop – 2016-03-25 07:09:59

@TheInternet：是单线程？ – 2016-04-04 14:11:14

您也可以使用ST monad，它允许您编写命令式代码，但安全地暴露纯功能性接口。

来源

2009-05-31 20:20:44

阵列在Haskell并不像你想象的那样的效率非常低，但在Haskell典型的做法很可能会实现这种使用普通的数据类型，如：

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

如果我解决这个问题，我可能会先将列表元素填充到数组中，从而更容易为堆创建编制索引。

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

如果您使用的是二进制最大堆，你可能要保持堆的大小的轨迹，你删除的元素，所以你可以在O（日志N）的右下角元素的时间。您还可以看看其他类型的堆，这些堆通常不是使用数组实现的，如二项堆和斐波那契堆。

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

来源

2009-05-31 20:50:25

作为哈斯克尔的一个练习，我实现了ST Monad的命令heapsort。

{-# 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

btw我比赛，如果它不是纯粹的功能，那么在Haskell这样做没有意义。我认为我的玩具实现比使用模板的C++实现的更好，将内容传递给内部函数。

来源

2009-06-05 23:40:53 yairchu

乔恩·费尔贝恩于1997年发布了功能堆排序的哈斯克尔咖啡邮件列表回：

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

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

我很惊讶treefold不在标准的前奏，因为它是如此有用。从我在思考1992年10月写的版本翻译 - 乔恩·费尔贝恩

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 (f a b : pairfold l) 
    where 
     pairfold (x:y:rest) = f x y : 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 [email protected](Node a heaps_a) [email protected](Node b heaps_b) 
      | a < b = Node a (node_b: heaps_a) 
      | otherwise = Node b (node_a: heaps_b)

来源

2010-02-02 19:01:00