Есть ли простой способ реализовать очередь с быстрым приоритетом в Haskell?

Question

Я немного погуглил и нашел статью о Finger Trees, которую можно использовать для реализации очереди приоритетов с надлежащей асимптотической сложностью, но они довольно сложные, но все же о самой простой вещи, которую я смог найти.

Существует ли простая структура данных, которая позволяет реализовать очередь с быстрым приоритетом в Haskell? Думайте просто, как вы могли бы объяснить это начинающему программисту.

Answer 1

Пакет кучи на Hackage утверждает, что основан на левой куче Окасаки.

Из документов:

Выберите MinHeap или MaxHeap, если вам нужна простая минимальная или максимальная куча (которая всегда сохраняет минимальный / максимальный элемент во главе кучи).

Если вы хотите вручную аннотировать значение с приоритетом, например, действие IO () с Int, используйте MinPrioHeap или MaxPrioHeap. Они управляют (prio, val) кортежами так, что только приоритет (а не значение) влияет на порядок элементов.

Если вам все еще нужно что-то другое, определите пользовательский порядок для элементов кучи, реализовав экземпляр HeapItem, и сообщите сопровождающему, что отсутствует.

Answer 2

Куча, которую проще всего реализовать на Хаскеле, которую я знаю, это Куча сопряжения.

Он поддерживает вставку и объединение в постоянное время (амортизированное) и логарифмическое время для удаления элементов.

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