-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Heaps in Haskell
--
-- A flexible Haskell heap implementation
@package heap
@version 0.2
-- | 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.
module Data.Heap
-- | The basic Heap type.
data Heap p a
-- | A Heap which will always extract the minimum first.
type MinHeap a = Heap MinPolicy a
-- | A Heap with inverted order: The maximum will be extracted
-- first.
type MaxHeap a = Heap MaxPolicy a
-- | The HeapPolicy class defines an order on the elements contained
-- within a Heap.
class HeapPolicy p a
heapCompare :: (HeapPolicy p a) => p -> a -> a -> Ordering
-- | Policy type for a MinHeap.
data MinPolicy
-- | Policy type for a MaxHeap
data MaxPolicy
-- | O(1). Is the Heap empty?
null :: Heap p a -> Bool
-- | O(1). Is the Heap empty?
isEmpty :: Heap p a -> Bool
-- | O(n). The number of elements in the Heap.
size :: (Num n) => Heap p a -> n
-- | O(1). Finds the minimum (depending on the HeapPolicy) of
-- the Heap.
head :: (HeapPolicy p a) => Heap p a -> a
-- | O(1). Constructs an empty Heap.
empty :: Heap p a
-- | O(1). Create a singleton Heap.
singleton :: a -> Heap p a
-- | O(log n). Insert an element in the Heap.
insert :: (HeapPolicy p a) => a -> Heap p a -> Heap p a
-- | O(log n). Delete the minimum (depending on the
-- HeapPolicy) from the Heap.
tail :: (HeapPolicy p a) => Heap p a -> Heap p a
-- | O(log n). Find the minimum (depending on the HeapPolicy)
-- and delete it from the Heap.
extractHead :: (HeapPolicy p a) => Heap p a -> (a, Heap p a)
-- | O(log max(n, m)). The union of two Heaps.
union :: (HeapPolicy p a) => Heap p a -> Heap p a -> Heap p a
-- | Builds the union over all given Heaps.
unions :: (HeapPolicy p a) => [Heap p a] -> Heap p a
-- | Removes all elements from a given Heap that do not fulfil the
-- predicate.
filter :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> Heap p a
-- | Partition the Heap into two. partition p h = (h1,
-- h2): All elements in h1 fulfil the predicate p,
-- those in h2 don't. union h1 h2 = h.
partition :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> (Heap p a, Heap p a)
-- | Take the lowest n elements in ascending order of the
-- Heap (according to the HeapPolicy).
take :: (HeapPolicy p a) => Int -> Heap p a -> [a]
-- | Remove the lowest (according to the HeapPolicy) n
-- elements from the Heap.
drop :: (HeapPolicy p a) => Int -> Heap p a -> Heap p a
-- | splitAt n h returns an ascending list of the lowest
-- n elements of h (according to its HeapPolicy)
-- and a Heap like h, lacking those elements.
splitAt :: (HeapPolicy p a) => Int -> Heap p a -> ([a], Heap p a)
-- | takeWhile p h lists the longest prefix of elements in
-- ascending order (according to its HeapPolicy) of h
-- that satisfy p.
takeWhile :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> [a]
-- | span p h returns the longest prefix of elements in
-- ascending order (according to its HeapPolicy) of h
-- that satisfy p and a Heap like h, lacking
-- those elements.
span :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> ([a], Heap p a)
-- | break p h returns the longest prefix of elements in
-- ascending order (according to its HeapPolicy) of h
-- that do not satisfy p and a Heap like
-- h, lacking those elements.
break :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> ([a], Heap p a)
-- | Builds a Heap from the given elements. You may want to use
-- fromAscList, if you have a sorted list.
fromList :: (HeapPolicy p a) => [a] -> Heap p a
-- | O(n). Lists elements of the Heap in no specific order.
toList :: Heap p a -> [a]
-- | O(n). Lists elements of the Heap in no specific order.
elems :: Heap p a -> [a]
-- | 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.
fromAscList :: (HeapPolicy p a) => [a] -> Heap p a
-- | O(n). Lists elements of the Heap in ascending order
-- (corresponding to the HeapPolicy).
toAscList :: (HeapPolicy p a) => Heap p a -> [a]
-- | Sanity checks for debugging. This includes checking the ranks and the
-- heap and leftist (the left rank is at least the right rank)
-- properties.
check :: (HeapPolicy p a) => Heap p a -> Bool
instance (Ord a) => HeapPolicy MaxPolicy a
instance (Ord a) => HeapPolicy MinPolicy a
instance (HeapPolicy p a, Read a) => Read (Heap p a)
instance Foldable (Heap p)
instance (HeapPolicy p a) => Monoid (Heap p a)
instance (HeapPolicy p a) => Ord (Heap p a)
instance (HeapPolicy p a) => Eq (Heap p a)
instance (Show a) => Show (Heap p a)