纯功能语言中的高效堆

Question

作为Haskell的一个练习,我正在尝试实现heapsort.堆通常在命令式语言中实现为数组,但在纯函数式语言中这将是非常低效的.所以我看了二进制堆,但到目前为止我发现的所有内容都是从命令性的角度描述的,所提出的算法很难转化为功能设置.如何在Haskell等纯函数式语言中有效地实现堆？

编辑:通过有效我的意思是它应该仍然在O(n*log n),但它不必击败C程序.另外,我想使用纯函数式编程.在Haskell中做这件事还有什么意义呢？

Answer 1

在Okasaki的Purely Functional Data Structures的附录中有许多Haskell堆实现.(源代码可以在链接下载.本书非常值得阅读.)它们本身都不是二进制堆,但"左派"堆非常相似.它具有O(log n)插入,删除和合并操作.还有更复杂的数据结构,如偏斜堆,二项式堆和展开堆,它们具有更好的性能.

Answer 2

Jon Fairbairn在1997年向Haskell Cafe邮件列表发布了一个功能性的堆栈:

http://www.mail-archive.com/haskell@haskell.org/msg01788.html

我在下面重现它,重新格式化以适应这个空间.我还略微简化了merge_heap的代码.

我很惊讶树折不是标准的前奏,因为它非常有用.翻译于1992年10月我在Ponder中写的版本 - 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 (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 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

您也可以使用STmonad,它允许您编写命令式代码,但安全地公开纯粹的功能接口.

Answer 4

作为Haskell的一个练习,我实施了ST Monad的强制性剪辑.

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

顺便说一下,如果它不是纯粹的功能,那么在Haskell中没有任何意义.我认为我的玩具实现比使用模板在C++中实现的更好,将内容传递给内部函数.