纯函数式语言中的高效堆

StackOverflow https://stackoverflow.com/questions/932721

题

作为 Haskell 的练习，我正在尝试实现堆排序。在命令式语言中，堆通常被实现为数组，但这在纯函数式语言中效率非常低。因此，我研究了二进制堆，但到目前为止我发现的所有内容都是从命令式的角度描述它们的，并且所提出的算法很难转化为函数设置。如何用Haskell这样的纯函数式语言高效地实现堆？

编辑： 我所说的高效是指它仍然应该是 O(n*log n)，但它不必击败 C 程序。另外，我想使用纯函数式编程。在 Haskell 中这样做还有什么意义呢？

有帮助吗？

解决方案

Okasaki 的附录中有许多 Haskell 堆实现 纯函数式数据结构. 。（源代码可以在链接中下载。这本书本身非常值得一读。）它们本身都不是二进制堆，但是 “左派”堆 非常相似。它具有 O(log n) 插入、删除和合并操作。还有更复杂的数据结构，例如 倾斜堆, 二项式堆, ， 和 展开堆 哪些具有更好的性能。

其他提示

乔恩费尔贝恩张贴的官能堆排序到Haskell的咖啡馆的邮件列表早在1997年：

http://www.mail-archive.com/haskell@ haskell.org/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 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)

您也可以使用ST单子，它允许你写势在必行代码，但安全接触的纯功能的界面。

如在Haskell练习，我实现与ST单子势在必行堆排序。

{-# 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 ++中使用模板实现更漂亮，周围的东西传递给内部函数。

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

在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的堆排序，看你怎么喜欢它。

我试图端口标准的二进制堆到功能设置。有与所描述的想法的文章：从功能语法谈标准二叉堆。所有文章中的源代码清单是在Scala中。但它也可能被移植很容易进入其他任何功能性的语言。

下面是包含堆排序的ML版本的页面。这是相当详细，应该提供一个良好的起点。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top