Effiziente Heaps in rein funktionalen Sprachen

Question

Als Übung in Haskell versuche ich, einen Heapsort zu implementieren. Der Heap wird normalerweise als ein Array in Imperativsprachen implementiert, aber dies wäre in rein funktionalen Sprachen äußerst ineffizient. Ich habe mich also mit binären Haufen beschäftigt, aber alles, was ich bisher gefunden habe, beschreibt sie aus einem zwingenden Blickwinkel und die vorgestellten Algorithmen sind schwer in eine funktionale Umgebung zu übersetzen. Wie kann man einen Heap effizient in einer rein funktionalen Sprache wie Haskell implementieren?

Edit: Mit effizienten ich meine, es sollte immer noch in O (n * log n), aber es muss nicht ein C-Programm zu schlagen. Außerdem würde ich gerne rein funktionale Programmierung verwenden. Was würde es sonst noch in Haskell machen?

Answer 1

In einem Anhang zu Okasakis Purely Functional Data Structures befinden sich einige Haskell Heap-Implementierungen. (Der Quellcode kann unter dem Link heruntergeladen werden. Das Buch selbst ist es wert, gelesen zu werden.) Keiner von ihnen sind binäre Haufen per se, aber die "leftist" heap ist sehr ähnlich. Es hat O (log n) Operationen zum Einfügen, Entfernen und Zusammenführen. Es gibt auch kompliziertere Datenstrukturen wie skew heaps, und splay heaps, die eine bessere Leistung haben.

Answer 2

Hier ist eine Seite mit einer ML-Version von HeapSort. Es ist ziemlich detailliert und sollte einen guten Ausgangspunkt bieten.

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

Answer 3

Genau wie in effizientem Quicksort Algorithmen in Haskell geschrieben, müssen Sie Monaden (state Transformatoren) verwenden Materialien an Ort und Stelle zu tun.

Answer 4

Sie könnten auch die ST Monade verwenden, mit der Sie imperative Code schreiben können, aber eine rein funktionale Schnittstelle sicher freilegen.

Answer 5

Arrays in Haskell sind nicht so extrem ineffizient wie Sie vielleicht denken, aber typische Praxis in Haskell würde wahrscheinlich dies mit normalen Datentypen zu implementieren sein, wie folgt aus:

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 

Wenn ich die Lösung dieses Problems wurden , Könnte ich beginnen, indem ich die Listenelemente in ein Array stopfe, was es einfacher macht, sie für die Heap-Erstellung zu indizieren.

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

Wenn Sie eine binäre max Heap verwenden, könnte man den Überblick über die Größe des Haufens halten wollen, wie Sie Elemente entfernen, so dass Sie die rechte untere Element in O (log N) finden kann Zeit. Sie können auch andere Arten von Heaps betrachten, die normalerweise nicht mit Arrays implementiert werden, wie Binomial-Heaps und Fibonacci-Heaps.

Eine letzte Anmerkung zur Array-Leistung: In Haskell gibt es einen Kompromiss zwischen der Verwendung von statischen Arrays und der Verwendung von veränderbaren Arrays. Bei statischen Arrays müssen Sie beim Ändern der Elemente neue Kopien der Arrays erstellen. Mit veränderbaren Arrays ist es für den Garbage Collector schwierig, verschiedene Objektgenerationen getrennt zu halten. Versuchen Sie, den Heapsort mit einem STArray zu implementieren und sehen Sie, wie es Ihnen gefällt.

Answer 6

Als Übung in Haskell implementierte ich einen imperativen Heapsort mit der 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 

btw, dass ich bestreiten, wenn sie nicht rein funktional ist dann macht es keinen Sinn, so in Haskell zu tun. Ich denke, dass meine Spielzeugimplementierung viel schöner ist als das, was man in C++ mit Templates erreichen und Dinge an die inneren Funktionen weitergeben würde.

Answer 7

Jon Fairbairn hat einen funktionalen Heapsort zur Haskell Cafe Mailing-Liste im Jahr 1997 zurück:

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

ich es neu formatierte reproduzieren unten, um diesen Raum zu passen. Ich habe auch den Code von merge_heap etwas vereinfacht.

Ich bin überrascht, treefold ist nicht im Standardauftakt, da es so nützlich ist. Übersetzt aus der Version, die ich in Ponder schrieb im Oktober 1992 - 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 8

Und hier ein Fibonacci-Heap in Haskell:

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

Hier sind die PDF-Datei für eine andere k-ary Haufen basierend auf Okasakis Arbeit.

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

Answer 9

Ich habe versucht, in den Hafen Standardbinärdistributionen Heap in Funktionseinstellungen. Es gibt einen Artikel mit beschriebener Idee: A Functional Approach to Standard Binary Heaps. Alle Quellcode-Auflistungen in dem Artikel befinden sich in Scala. Aber es könnte sehr leicht in jede andere funktionale Sprache portiert werden.