38

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

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

4

9 回答 9

34

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

于 2009-05-31T21:53:54.383 回答
12

Jon Fairbairn 早在 1997 年就在 Haskell Cafe 邮件列表中发布了一个函数堆排序：

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)
于 2010-02-02T19:01:00.977 回答
11

您还可以使用STmonad，它允许您编写命令式代码，但安全地公开一个纯函数式接口。

于 2009-05-31T20:20:44.383 回答
8

作为 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++ 中实现的要好得多，将东西传递给内部函数。

于 2009-06-05T23:40:53.817 回答
3

这是 Haskell 中的斐波那契堆：

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

以下是基于 Okasaki 工作的其他一些 k-ary 堆的 pdf 文件。

https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

于 2012-08-17T08:56:19.637 回答
2

就像用 Haskell 编写的高效快速排序算法一样，您需要使用 monads（状态转换器）来就地执行操作。

于 2009-05-31T20:20:35.163 回答
2

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(log N) 时间内找到右下角的元素。您还可以查看通常不使用数组实现的其他类型的堆，例如二项式堆和斐波那契堆。

关于数组性能的最后一点说明：在 Haskell 中，使用静态数组和使用可变数组之间存在权衡。对于静态数组，您必须在更改元素时创建数组的新副本。对于可变数组，垃圾收集器很难将不同代的对象分开。尝试使用 STArray 实现堆排序，看看你喜欢它。

于 2009-05-31T20:50:25.027 回答
2

我试图将标准二进制堆移植到功能设置中。有一篇文章描述了这个想法：A Functional Approach to Standard Binary Heaps。文章中的所有源代码清单都在 Scala 中。但它可能很容易移植到任何其他函数式语言中。

于 2014-01-15T17:14:16.640 回答
1

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

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

于 2009-05-31T19:59:30.043 回答