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
action with anIO
()Int
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]
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 MaxHeap a = Heap MaxPolicy aSource
A Heap
with inverted order: The maximum will be extracted first.
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 not partial.
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
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. You may want to use fromAscList
,
if you have a sorted list.
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). 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
).