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.
Create an empty PairingHeap.
Inserts a new element into a PairingHeap.
Complexity: O(1)
Merges two PairingHeaps 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 3Removes 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)
A
PairingHeaphas comparable keys and values of an arbitrary type.