A flexible implementation of min-, max- and custom-priority heaps based on the leftist-heaps from Chris Okasaki's book "Purely Functional Data Structures", Cambridge University Press, 1998, chapter 3.1.
There are different flavours of Heap
s, each of them following a different
strategy when ordering its elements:
- Choose
MinHeap
orMaxHeap
if you need a simple minimum or maximum heap (which always keeps the minimum/maximum element at the head of theHeap
). - If you wish to manually annotate a value with a priority, e. g. an
IO ()
action with anInt
useMinPrioHeap
orMaxPrioHeap
. They manage(priority, value)
tuples so that only the priority (and not the value) influences the order of elements. - If you still need something different, define a custom order for the heap
elements by implementing a
HeapPolicy
and let the maintainer know, what's missing.
This module is best imported qualified
in order to prevent name clashes
with other modules.
- data Heap p a
- type MinHeap a = Heap MinPolicy a
- type MaxHeap a = Heap MaxPolicy a
- type MinPrioHeap priority value = Heap FstMinPolicy (priority, value)
- type MaxPrioHeap priority value = Heap FstMaxPolicy (priority, value)
- class HeapPolicy p a where
- heapCompare :: p -> a -> a -> Ordering
- data MinPolicy
- data MaxPolicy
- data FstMinPolicy
- data FstMaxPolicy
- null :: Heap p a -> Bool
- isEmpty :: Heap p a -> Bool
- size :: Heap p a -> Int
- head :: HeapPolicy p a => Heap p a -> a
- tail :: HeapPolicy p a => Heap p a -> Heap p a
- view :: HeapPolicy p a => Heap p a -> Maybe (a, Heap p a)
- extractHead :: HeapPolicy p a => Heap p a -> (a, Heap p a)
- empty :: Heap p a
- singleton :: a -> Heap p a
- insert :: HeapPolicy p a => a -> Heap p a -> Heap p a
- union :: HeapPolicy p a => Heap p a -> Heap p a -> Heap p a
- unions :: HeapPolicy p a => [Heap p a] -> Heap p a
- filter :: HeapPolicy p a => (a -> Bool) -> Heap p a -> Heap p a
- partition :: HeapPolicy p a => (a -> Bool) -> Heap p a -> (Heap p a, Heap p a)
- take :: HeapPolicy p a => Int -> Heap p a -> [a]
- drop :: HeapPolicy p a => Int -> Heap p a -> Heap p a
- splitAt :: HeapPolicy p a => Int -> Heap p a -> ([a], Heap p a)
- takeWhile :: HeapPolicy p a => (a -> Bool) -> Heap p a -> [a]
- dropWhile :: HeapPolicy p a => (a -> Bool) -> Heap p a -> Heap p a
- span :: HeapPolicy p a => (a -> Bool) -> Heap p a -> ([a], Heap p a)
- break :: HeapPolicy p a => (a -> Bool) -> Heap p a -> ([a], Heap p a)
- fromList :: HeapPolicy p a => [a] -> Heap p a
- toList :: Heap p a -> [a]
- elems :: Heap p a -> [a]
- fromAscList :: HeapPolicy p a => [a] -> Heap p a
- toAscList :: HeapPolicy p a => Heap p a -> [a]
- fromDescList :: HeapPolicy p a => [a] -> Heap p a
- toDescList :: HeapPolicy p a => Heap p a -> [a]
Types
Various heap flavours
The basic Heap
type.
HeapPolicy p a => Eq (Heap p a) | |
HeapPolicy p a => Ord (Heap p a) | |
(HeapPolicy p a, Read a) => Read (Heap p a) | |
Show a => Show (Heap p a) | |
HeapPolicy p a => Monoid (Heap p a) |
type MinPrioHeap priority value = Heap FstMinPolicy (priority, value)Source
type MaxPrioHeap priority value = Heap FstMaxPolicy (priority, value)Source
Ordering policies
class HeapPolicy p a whereSource
The HeapPolicy
class defines an order on the elements contained within
a Heap
.
:: p | Must not be evaluated. |
-> a | Compared to 3rd parameter. |
-> a | Compared to 2nd parameter. |
-> Ordering | Result of the comparison. |
Compare two elements, just like compare
of the Ord
class, so this
function has to define a mathematical ordering. When using a HeapPolicy
for a Heap
, the minimal value (defined by this order) will be the head
of the Heap
.
Ord a => HeapPolicy MaxPolicy a | |
Ord a => HeapPolicy MinPolicy a | |
Ord priority => HeapPolicy FstMaxPolicy (priority, value) | |
Ord priority => HeapPolicy FstMinPolicy (priority, value) |
data FstMinPolicy Source
Policy type for a (priority, value)
MinPrioHeap
.
Ord priority => HeapPolicy FstMinPolicy (priority, value) |
data FstMaxPolicy Source
Policy type for a (priority, value)
MaxPrioHeap
.
Ord priority => HeapPolicy FstMaxPolicy (priority, value) |
Query
head :: HeapPolicy p a => Heap p a -> aSource
O(1). Returns the first item of the Heap
, according to its HeapPolicy
.
Warning: This function issues an error
for empty Heap
s, please consider
using the view
function instead, it's safe.
tail :: HeapPolicy p a => Heap p a -> Heap p aSource
view :: HeapPolicy p a => Heap p a -> Maybe (a, Heap p a)Source
O(log n) for the tail, O(1) for the head. Find the minimum (depending
on the HeapPolicy
) and delete it from the Heap
(i. e. find head and tail
of a heap) if it is not empty. Otherwise, Nothing
is returned.
extractHead :: HeapPolicy p a => Heap p a -> (a, Heap p a)Source
Construction
union :: HeapPolicy p a => Heap p a -> Heap p a -> Heap p aSource
O(log max(n, m)). The union of two Heap
s.
Filter
filter :: HeapPolicy p a => (a -> Bool) -> Heap p a -> Heap p aSource
Removes all elements from a given Heap
that do not fulfil the predicate.
Subranges
take :: HeapPolicy p a => Int -> Heap p a -> [a]Source
Take the lowest n
elements in ascending order of the Heap
(according
to the HeapPolicy
).
drop :: HeapPolicy p a => Int -> Heap p a -> Heap p aSource
Remove the lowest (according to the HeapPolicy
) n
elements
from the Heap
.
splitAt :: HeapPolicy p a => Int -> Heap p a -> ([a], Heap p a)Source
returns an ascending list of the lowest splitAt
n hn
elements of h
(according to its HeapPolicy
) and a Heap
like h
, lacking those elements.
takeWhile :: HeapPolicy p a => (a -> Bool) -> Heap p a -> [a]Source
lists the longest prefix of elements in ascending order
(according to its takeWhile
p hHeapPolicy
) of h
that satisfy p
.
dropWhile :: HeapPolicy p a => (a -> Bool) -> Heap p a -> Heap p aSource
removes the longest prefix of elements from dropWhile
p hh
that
satisfy p
.
span :: HeapPolicy p a => (a -> Bool) -> Heap p a -> ([a], Heap p a)Source
returns the longest prefix of elements in ascending order
(according to its span
p hHeapPolicy
) of h
that satisfy p
and a Heap
like
h
, with those elements removed.
break :: HeapPolicy p a => (a -> Bool) -> Heap p a -> ([a], Heap p a)Source
returns the longest prefix of elements in ascending order
(according to its break
p hHeapPolicy
) of h
that do not satisfy p
and a Heap
like h
, with those elements removed.
Conversion
List
fromList :: HeapPolicy p a => [a] -> Heap p aSource
Builds a Heap
from the given elements. Assuming you have a sorted list,
you may want to use fromDescList
or fromAscList
, they are both faster
than this function.
Ordered list
fromAscList :: HeapPolicy p a => [a] -> Heap p aSource
O(n). Creates a Heap
from an ascending list. Note that the list has to
be ascending corresponding to the HeapPolicy
, not to its Ord
instance
declaration (if there is one). This function is faster than fromList
but
not as fast as fromDescList
.
The precondition is not checked.
toAscList :: HeapPolicy p a => Heap p a -> [a]Source
O(n). Lists elements of the Heap
in ascending order (corresponding to
the HeapPolicy
).
fromDescList :: HeapPolicy p a => [a] -> Heap p aSource
O(n). Create a Heap
from a descending list. Note that the list has to
be descending corresponding to the HeapPolicy
, not to its Ord
instance
declaration (if there is one). This function is provided, because it is much
faster than fromList
and fromAscList
.
The precondition is not checked.
toDescList :: HeapPolicy p a => Heap p a -> [a]Source
O(n). Lists the elements on the Heap
in descending order (corresponding
to the HeapPolicy
). Note that this function is not especially efficient (it
is implemented as
), it is just provided as a
counterpart of the very efficient reverse
. toAscList
fromDescList
function.