-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Heaps in Haskell -- -- A flexible Haskell heap implementation @package heap @version 0.4.0 -- | 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 Heaps, each of them following a -- different strategy when ordering its elements: -- -- -- -- 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 -- | A Heap storing priority-value-associations. It only regards the -- priority for determining the order of elements, the tuple with minimal -- fst value (i. e. priority) will always be the head of the -- Heap. type MinPrioHeap priority value = Heap FstMinPolicy (priority, value) -- | A Heap storing priority-value-associations. It only regards the -- priority for determining the order of elements, the tuple with maximal -- fst value (i. e. priority) will always be the head of the -- Heap. type MaxPrioHeap priority value = Heap FstMaxPolicy (priority, value) -- | 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 -- | Policy type for a (priority, value) MinPrioHeap. data FstMinPolicy -- | Policy type for a (priority, value) MaxPrioHeap. data FstMaxPolicy -- | 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). Returns the first item of the Heap, according to -- its HeapPolicy. -- -- Warning: This function issues an error for empty -- Heaps, please consider using the view function instead, -- it's not partial. head :: (HeapPolicy p a) => Heap p a -> a -- | O(log n). Returns the Heap with the head removed. -- -- Warning: This function issues an error for empty -- Heaps, please consider using the view function instead, -- it's not partial. tail :: (HeapPolicy p a) => Heap p a -> Heap p a -- | 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. view :: (HeapPolicy p a) => Heap p a -> Maybe (a, Heap p a) -- | O(log n). Returns head and tail of a Heap. -- -- Warning: This function issues an error for empty -- Heaps, please consider using the view function instead, -- it's not partial. extractHead :: (HeapPolicy p a) => Heap p a -> (a, Heap p 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 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] -- | dropWhile p h removes the longest prefix of elements -- from h that satisfy p. dropWhile :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> Heap p 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, with those -- elements removed. 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, with those elements removed. 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] instance (Ord priority) => HeapPolicy FstMaxPolicy (priority, value) instance (Ord priority) => HeapPolicy FstMinPolicy (priority, value) 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)