haskell - Haskellで高速プライオリティキューを実装する簡単な方法はありますか?

Question

少しグーグルで検索して、Finger Treesに関する論文を見つけました。これは、適切な漸近的な複雑さで優先キューを実装するために使用できますが、それらは非常に複雑ですが、それでも私が見つけることができる最も単純なものです.

Haskell で高速優先キューを実装できる単純なデータ構造はありますか? 初心者のプログラマーに説明できるように、簡単に 考えてください。

Answer 1

私が知っている Haskell で最も簡単に実装できるヒープはPairing Heapです。

要素を削除するための一定時間 (償却) および対数時間での挿入とマージをサポートします。

data Heap a = Empty | Heap a [(Heap a)]
    deriving Show

findMin :: Heap a -> a
findMin (Heap h _) = h

merge :: Ord a => Heap a -> Heap a -> Heap a
merge Empty h = h
merge h Empty = h
merge h1@(Heap x hs1) h2@(Heap y hs2)
    | x < y     = Heap x (h2:hs1)
    | otherwise = Heap y (h1:hs2)

mergePairs :: Ord a => [Heap a] -> Heap a
mergePairs []           = Empty
mergePairs [h]          = h
mergePairs (h1:h2:hs)   = merge (merge h1 h2) (mergePairs hs)

insert :: Ord a => a -> Heap a -> Heap a
insert x = merge (Heap x [])

deleteMin :: Ord a => Heap a -> Heap a
deleteMin (Heap x hs) = mergePairs hs