纯函数语言中的高效堆

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

早在1997年,JonFairbairn就在Haskell咖啡馆的邮件列表中发布了一个功能性的heapsort:

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

我在下面复制它,重新格式化以适应这个空间。我还稍微简化了合并堆的代码。

我很惊讶特雷福没有出现在标准序曲中,因为它是如此有用。翻译自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 monad,它允许您编写命令式代码,但安全地公开一个纯粹的函数式接口。

作为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

顺便说一句,我认为如果这不是纯粹的功能,那么在哈斯克尔这样做没有意义。我认为我的玩具实现比在模板中用C++实现的东西要好得多,把东西传递给内部函数。

这里是哈斯克尔的斐波那契堆:

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

以下是基于冈崎工作的其他k-ary堆的PDF文件。

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

就像在Haskell编写的高效快速排序算法中一样,您需要使用monads(状态转换器)来完成相应的工作。

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 = ...

如果使用的是二进制max堆,那么在删除元素时可能需要跟踪堆的大小,以便在o(log n)时间内找到右下角的元素。您还可以看看其他类型的堆,它们通常不是使用数组实现的,比如二项式堆和斐波那契堆。

关于数组性能的最后一个注意事项:在Haskell中,使用静态数组和使用可变数组之间存在一种权衡。对于静态数组,更改元素时必须创建数组的新副本。对于可变数组,垃圾收集器很难将不同代的对象分隔开。尝试使用starray实现heapsort,看看你喜欢它。

我尝试将标准二进制堆移植到函数设置中。有一篇文章阐述了以下观点: A Functional Approach to Standard Binary Heaps . 本文中的所有源代码列表都在scala中。但它可以很容易地移植到任何其他功能语言中。

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

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