A flexible implementation of min-, max- or custom-priority heaps based on the leftist-heaps from Chris Okasaki's book "Purely Functional Data Structures", Cambridge University Press, 1998, chapter 3.1.
If you need a minimum or maximum heap, use MinHeap
resp. MaxHeap
. If
you want to define a custom order of the heap elements implement a
HeapPolicy
.
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
- class HeapPolicy p a where
- heapCompare :: p -> a -> a -> Ordering
- data MinPolicy
- data MaxPolicy
- null :: Heap p a -> Bool
- isEmpty :: Heap p a -> Bool
- size :: Num n => Heap p a -> n
- head :: HeapPolicy p a => Heap p a -> a
- tail :: HeapPolicy p a => Heap p 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]
- 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]
- check :: HeapPolicy p a => Heap p a -> Bool
Heap type
The basic Heap
type.
Foldable (Heap p) | |
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.
class HeapPolicy p a whereSource
The HeapPolicy
class defines an order on the elements contained within
a Heap
.
:: p | Must not be evaluated. |
-> a | Must be compared to 3rd parameter. |
-> a | Must be compared to 2nd parameter. |
-> Ordering | Result of the comparison. |
Ord a => HeapPolicy MaxPolicy a | |
Ord a => HeapPolicy MinPolicy a |
Query
head :: HeapPolicy p a => Heap p a -> aSource
O(1). Finds the minimum (depending on the HeapPolicy
) of the Heap
.
tail :: HeapPolicy p a => Heap p a -> Heap p aSource
O(log n). Delete the minimum (depending on the HeapPolicy
)
from the Heap
.
extractHead :: HeapPolicy p a => Heap p a -> (a, Heap p a)Source
O(log n). Find the minimum (depending on the HeapPolicy
) and
delete it from the Heap
. This function is undefined for an
empty Heap
.
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
.
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
, lacking those elements.
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
, lacking those elements.
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
).
Debugging
check :: HeapPolicy p a => Heap p a -> BoolSource
Sanity checks for debugging. This includes checking the ranks and the heap and leftist (the left rank is at least the right rank) properties.