This is a simple pairing heap implementation written in Elm usable as a priority queue. This code is based heavily on the pseudocode available at the Wikipedia page.
A PairingHeap
has comparable keys and values of an arbitrary type.
Create an empty PairingHeap.
Inserts a new element into a PairingHeap
.
Complexity: O(1)
Merges two PairingHeap
s together into one new heap containing all of the key-value pairs from both inputs.
Complexity: O(1)
Find the minimum value in a heap returning Nothing if the heap is empty.
Complexity: O(1)
findMin (fromList [(10, ()), (3, ()), (8, ())]) == Just 3
Removes the minimum element from a PairingHeap
returning a new heap without that element.
This will return an empty heap if given an empty heap as input.
Complexity: O(log n)
This function turns a list of key-value pairs into a PairingHeap
.
Complexity: O(n)
This function turns a PairingHeap
into a sorted list of key-value pairs.
Complexity: O(n log n)
module PairingHeap exposing (PairingHeap, empty, findMin, merge, insert, deleteMin, fromList, toSortedList)
{-| This is a simple pairing heap implementation written in Elm usable as a priority queue. This code is
based heavily on the pseudocode available at [the Wikipedia page](https://en.wikipedia.org/wiki/Pairing_heap).
# Type and Constructor
@docs PairingHeap, empty
# Operations
@docs insert, merge, findMin, deleteMin
# Convenience functions
@docs fromList, toSortedList
-}
import Maybe exposing (Maybe(..))
{-| A `PairingHeap` has comparable keys and values of an arbitrary type.
-}
type PairingHeap comparable a
= Empty
| Heap comparable a (List (PairingHeap comparable a))
{-| Create an empty PairingHeap.
-}
empty : PairingHeap comparable a
empty =
Empty
{-| Find the minimum value in a heap returning Nothing if the heap is empty.
Complexity: O(1)
findMin (fromList [(10, ()), (3, ()), (8, ())]) == Just 3
-}
findMin : PairingHeap comparable a -> Maybe (comparable, a)
findMin x =
case x of
Empty ->
Nothing
Heap k v _ ->
Just (k, v)
{-| Merges two `PairingHeap`s together into one new heap containing all of the key-value pairs from both inputs.
Complexity: O(1)
-}
merge : PairingHeap comparable a -> PairingHeap comparable a -> PairingHeap comparable a
merge heap1 heap2 =
case ( heap1, heap2 ) of
( Empty, _ ) ->
heap2
( _, Empty ) ->
heap1
( Heap k1 v1 hs1, Heap k2 v2 hs2 ) ->
if k1 < k2 then
Heap k1 v1 (heap2 :: hs1)
else
Heap k2 v2 (heap1 :: hs2)
{-| Inserts a new element into a `PairingHeap`.
Complexity: O(1)
-}
insert : (comparable, a) -> PairingHeap comparable a -> PairingHeap comparable a
insert (k, v) heap =
merge (Heap k v []) heap
{-| Removes the minimum element from a `PairingHeap` returning a new heap without that element.
This will return an empty heap if given an empty heap as input.
Complexity: O(log n)
-}
deleteMin : PairingHeap comparable a -> PairingHeap comparable a
deleteMin heap =
case heap of
Empty ->
Empty
Heap k v heaps ->
mergePairs heaps
{-| This is an internal function used by deleteMin.
-}
mergePairs : List (PairingHeap comparable a) -> PairingHeap comparable a
mergePairs heaps =
case heaps of
[] ->
Empty
x :: [] ->
x
x :: (y :: xs) ->
merge (merge x y) (mergePairs xs)
-- Extra convenience functions
{-| This function turns a list of key-value pairs into a `PairingHeap`.
Complexity: O(n)
-}
fromList : List (comparable, a) -> PairingHeap comparable a
fromList =
List.foldl insert empty
{-| This function turns a `PairingHeap` into a sorted list of key-value pairs.
Complexity: O(n log n)
-}
toSortedList : PairingHeap comparable a -> List (comparable, a)
toSortedList heap =
case heap of
Empty ->
[]
Heap k v _ ->
(k, v) :: (toSortedList (deleteMin heap))