-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Heaps in Haskell -- -- A flexible Haskell implementation of minimum, maximum, -- minimum-priority, maximum-priority and custom-ordered heaps. @package heap @version 1.0.2 -- | A flexible implementation of min-, max-, min-priority, max-priority -- 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: -- -- -- -- All sorts of heaps mentioned above (MinHeap, MaxHeap, -- MinPrioHeap and MaxPrioHeap) are built on the same -- underlying type: HeapT prio val. It is a simple -- minimum priority heap. The trick is, that you never insert (prio, -- val) pairs directly: You only insert an "external -- representation", usually called item, and an appropriate -- HeapItem instance is used to split the item to -- a (prio, val) pair. For details refer to the documentation of -- HeapItem. module Data.Heap -- | The basic heap type. It stores priority-value pairs (prio, -- val) and always keeps the pair with minimal priority on top. The -- value associated to the priority does not have any influence on the -- ordering of elements. data HeapT prio val -- | This type alias is an abbreviation for a HeapT which uses the -- HeapItem instance of pol item to organise its -- elements. type Heap pol item = HeapT (Prio pol item) (Val pol item) -- | A Heap which will always extract the minimum first. type MinHeap a = Heap MinPolicy a -- | A Heap which will always extract the maximum first. type MaxHeap a = Heap MaxPolicy a -- | A Heap storing priority-value pairs (prio, val). The -- order of elements is solely determined by the priority prio, -- the value val has no influence. The priority-value pair with -- minmal priority will always be extracted first. type MinPrioHeap prio val = Heap FstMinPolicy (prio, val) -- | A Heap storing priority-value pairs (prio, val). The -- order of elements is solely determined by the priority prio, -- the value val has no influence. The priority-value pair with -- maximum priority will always be extracted first. type MaxPrioHeap prio val = Heap FstMaxPolicy (prio, val) -- | HeapItem pol item is a type class for items that can -- be stored in a HeapT. A raw HeapT prio val only -- provides a minimum priority heap (i. e. val doesn't influence -- the ordering of elements and the pair with minimal prio will -- be extracted first, see HeapT documentation). The job of this -- class is to translate between arbitrary items and -- priority-value pairs (Prio pol item, Val pol -- item), depending on the policy pol to be used. This way, -- we are able to use HeapT not only as MinPrioHeap, but -- also as MinHeap, MaxHeap, MaxPrioHeap or a custom -- implementation. In short: The job of this class is to deconstruct -- arbitrary items into a (prio, val) pairs that can be -- handled by a minimum priority HeapT. -- -- Example: Consider you want to use HeapT prio val as a -- MaxHeap a. You would have to invert the order of -- a (e. g. by introducing newtype InvOrd a = InvOrd a -- along with an apropriate Ord instance for it) and then use a -- type MaxHeap a = HeapT (InvOrd a) (). You'd -- also have to translate every x to (InvOrd x, ()) -- before insertion and back after removal in order to retrieve your -- original type a. -- -- This functionality is provided by the HeapItem class. In the -- above example, you'd use a MaxHeap. The according instance -- declaration is of course already provided and looks like this -- (simplified): -- -- @data MaxPolicy -- -- instance (Ord a) => HeapItem MaxPolicy a where -- newtype Prio MaxPolicy a = MaxP a deriving (Eq) -- type Val MaxPolicy a = () split x = (MaxP x, ()) -- merge (MaxP x, _) = x -- -- instance (Ord a) => Ord (Prio MaxPolicy -- a) where compare (MaxP x) (MaxP y) = compare y x @ -- -- MaxPolicy is a phantom type describing which HeapItem -- instance is actually meant (e. g. we have to distinguish between -- MinHeap and MaxHeap, which is done via MinPolicy -- and MaxPolicy, respectively) and MaxP inverts the -- ordering of a, so that the maximum will be on top of the -- HeapT. -- -- The conversion functions split and merge have to make -- sure that -- --
    --
  1. forall p v. split (merge (p, v)) == (p, v) -- (merge and split don't remove, add or alter -- anything)
    2. --
  2. forall p v f. fst (split (merge (p, f v)) -- == fst (split (merge (p, v))) (modifying the -- associated value v doesn't alter the priority -- p)
    3. --
class Ord (Prio pol item) => HeapItem pol item where data family Prio pol item :: * type family Val pol item :: * split :: HeapItem pol item => item -> (Prio pol item, Val pol item) merge :: HeapItem pol item => (Prio pol item, Val pol item) -> item -- | Policy type for a MinHeap. data MinPolicy -- | Policy type for a MaxHeap. data MaxPolicy -- | Policy type for a (prio, val) MinPrioHeap. data FstMinPolicy -- | Policy type for a (prio, val) MaxPrioHeap. data FstMaxPolicy -- | O(1). Is the HeapT empty? isEmpty :: HeapT prio val -> Bool -- | O(1). Is the HeapT empty? null :: HeapT prio val -> Bool -- | O(1). The total number of elements in the HeapT. size :: HeapT prio val -> Int -- | O(1). Construct an empty HeapT. empty :: HeapT prio val -- | O(1). Create a singleton HeapT. singleton :: HeapItem pol item => item -> Heap pol item -- | O(log n). Insert a single item into the HeapT. insert :: HeapItem pol item => item -> Heap pol item -> Heap pol item -- | O(log max(n, m)). Form the union of two HeapTs. union :: Ord prio => HeapT prio val -> HeapT prio val -> HeapT prio val -- | Build the union of all given HeapTs. unions :: Ord prio => [HeapT prio val] -> HeapT prio val -- | O(1) for the head, O(log n) for the tail. Find the item -- with minimal associated priority and remove it from the Heap -- (i. e. find head and tail of the heap) if it is not empty. Otherwise, -- Nothing is returned. view :: HeapItem pol item => Heap pol item -> Maybe (item, Heap pol item) -- | O(1). Find the item with minimal associated priority on the -- Heap (i. e. its head) if it is not empty. Otherwise, -- Nothing is returned. viewHead :: HeapItem pol item => Heap pol item -> Maybe item -- | O(log n). Remove the item with minimal associated priority and -- from the Heap (i. e. its tail) if it is not empty. Otherwise, -- Nothing is returned. viewTail :: HeapItem pol item => Heap pol item -> Maybe (Heap pol item) -- | Remove all items from a HeapT not fulfilling a predicate. filter :: HeapItem pol item => (item -> Bool) -> Heap pol item -> Heap pol item -- | Partition the Heap into two. partition p h = (h1, -- h2): All items in h1 fulfil the predicate p, -- those in h2 don't. union h1 h2 = h. partition :: HeapItem pol item => (item -> Bool) -> Heap pol item -> (Heap pol item, Heap pol item) -- | Take the first n items from the Heap. take :: HeapItem pol item => Int -> Heap pol item -> [item] -- | Remove first n items from the Heap. drop :: HeapItem pol item => Int -> Heap pol item -> Heap pol item -- | splitAt n h: Return a list of the first n -- items of h and h, with those elements removed. splitAt :: HeapItem pol item => Int -> Heap pol item -> ([item], Heap pol item) -- | takeWhile p h: List the longest prefix of items in -- h that satisfy p. takeWhile :: HeapItem pol item => (item -> Bool) -> Heap pol item -> [item] -- | dropWhile p h: Remove the longest prefix of items in -- h that satisfy p. dropWhile :: HeapItem pol item => (item -> Bool) -> Heap pol item -> Heap pol item -- | span p h: Return the longest prefix of items in -- h that satisfy p and h, with those elements -- removed. span :: HeapItem pol item => (item -> Bool) -> Heap pol item -> ([item], Heap pol item) -- | break p h: The longest prefix of items in h -- that do not satisfy p and h, with those -- elements removed. break :: HeapItem pol item => (item -> Bool) -> Heap pol item -> ([item], Heap pol item) -- | O(n log n). Build a Heap from the given items. Assuming -- you have a sorted list, you probably want to use fromDescList -- or fromAscList, they are faster than this function. fromList :: HeapItem pol item => [item] -> Heap pol item -- | O(n log n). List all items of the Heap in no specific -- order. toList :: HeapItem pol item => Heap pol item -> [item] -- | O(n). Create a Heap from a list providing its items in -- ascending order of priority (i. e. in the same order they will be -- removed from the Heap). This function is faster than -- fromList but not as fast as fromDescList. -- -- The precondition is not checked. fromAscList :: HeapItem pol item => [item] -> Heap pol item -- | O(n log n). List the items of the Heap in ascending -- order of priority. toAscList :: HeapItem pol item => Heap pol item -> [item] -- | O(n). Create a Heap from a list providing its items in -- descending order of priority (i. e. they will be removed inversely -- from the Heap). Prefer this function over fromList and -- fromAscList, it's faster. -- -- The precondition is not checked. fromDescList :: HeapItem pol item => [item] -> Heap pol item -- | O(n log n). List the items of the Heap in descending -- order of priority. Note that this function is not especially efficient -- (it is implemented in terms of reverse and toAscList), -- it is provided as a counterpart of the efficient fromDescList -- function. toDescList :: HeapItem pol item => Heap pol item -> [item]