~s)      !"#$%&'(4The basic heap type. It stores priority-value pairs  (prio, val) and M always keeps the pair with minimal priority on top. The value associated to G the priority does not have any influence on the ordering of elements. )A tree node of a non-empty . *Rank of the leftist heap. + Number of elements in the heap. ,Priority of the entry. -Value of the entry. .Left subtree. /Right subtree. 0 An empty . O(1) . Is the  empty? 1O(1). Find the rank of a " (the length of its right spine). O(1)&. The total number of elements in the . O(1). Construct an empty . 2O(1). Create a singleton . 3O(1)). Insert an priority-value pair into the , whose / priority is  less or equal/ to all other priorities on the , i. e. a pair that is a  valid head of the . The precondition is not checked. O(log max(n, m)). Form the union of two s. 4Build a ' from a priority, a value and two more s. Therefore,  the  priority has to be less or equal than all priorities in both   parameters. The precondition is not checked. Build the union of all given s. 5O(log n) for the tail, O(1), for the head. Find the priority-value pair . with minimal priority and delete it from the  (i. e. find head and tail - of the heap) if it is not empty. Otherwise, 6 is returned. 7Partition the  into two. 7 p h = (h1, h2): All  priority-value pairs in h1 fulfil the predicate p , those in h2 don't.   h1 h2 = h. 88 n h: A list of the lowest n priority-value pairs of h, in # ascending order of priority, and h, with those elements removed. 99 p h0: The longest prefix of priority-value pairs of h, in + ascending order of priority, that satisfy p and h, with those elements  removed. : O(n log n) . Build a & from the given priority-value pairs. ; O(n log n)'. List all priority-value pairs of the  in no specific  order. <O(n) . Create a 3 from a list providing its priority-value pairs in  descending order of priority. The precondition is not checked. = O(n log n)'. List the priority-value pairs of the  in ascending  order of priority. >%List the priority-value pairs of the  just like = does,  but don't ignore the value val when sorting. )*+,-./0125789:;<=0)*+,-./)*+,-./0125789:;<=Policy type for a  (prio, val) . Policy type for a  (prio, val) . Policy type for a . Policy type for a .   pol item3 is a type class for items that can be stored in a  . A raw  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 ! documentation). The job of this ) class is to translate between arbitrary items and priority-value pairs  (  pol item,   pol item), depending on the policy pol to be used.  This way, we are able to use  not only as , but also as  , , + or a custom implementation. In short: The / job of this class is to deconstruct arbitrary item s into a  (prio, val) 1 pairs that can be handled by a minimum priority . "Example: Consider you want to use  prio val as a  a. You # would have to invert the order of a (e. g. by introducing newtype InvOrd a  = InvOrd a along with an apropriate ?! instance for it) and then use a  type  a =  (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   class. In the above example,  you'd use a 2. The according instance declaration is of course 4 already provided and looks like this (simplified):  data    instance (? a) =>    a where  newtype    a = MaxP a deriving (@)  type    a = ()    x = (MaxP x, ())   (MaxP x, _) = x   instance (? a) => ? (   a) where  A (MaxP x) (MaxP y) = A y x $ is a phantom type describing which   instance is actually - meant (e. g. we have to distinguish between  and  , which is  done via   and , respectively) and MaxP inverts the  ordering of a,, so that the maximum will be on top of the . The conversion functions   and  have to make sure that   forall p v.   ( (p, v)) == (p, v) ( and    don'!t remove, add or alter anything)  forall p v f. B (  ( (p, f v)) == B (   ( (p, v)))! (modifying the associated value v doesn' t alter the  priority p)  The part of item, that determines the order of elements on a . Everything not part of   pol item  Translate an item into a priority-value pair.  Restore the item from a priority-value pair. A  storing priority-value pairs  (prio, val). The order of elements & is solely determined by the priority prio , the value val has no influence. O The priority-value pair with maximum priority will always be extracted first. A  storing priority-value pairs  (prio, val). The order of elements & is solely determined by the priority prio , the value val has no influence. N The priority-value pair with minmal priority will always be extracted first. A . which will always extract the maximum first. A . which will always extract the minimum first. )This type alias is an abbreviation for a  which uses the    instance of pol item to organise its elements. C  a function on item"s to one on priority-value pairs.  C   CO(1) . Is the  empty? O(1). Create a singleton . O(log n) . Insert a single item into the . O(1) for the head, O(log n)* for the tail. Find the item with minimal , associated priority and remove it from the  (i. e. find head and tail - of the heap) if it is not empty. Otherwise, 6 is returned. O(1)8. Find the item with minimal associated priority on the  (i. e. * its head) if it is not empty. Otherwise, 6 is returned. O(log n)@. Remove the item with minimal associated priority and from the  1 (i. e. its tail) if it is not empty. Otherwise, 6 is returned. Remove all items from a  not fulfilling a predicate. Partition the  into two.  p h = (h1, h2): All items in  h1 fulfil the predicate p , those in h2 don't. union h1 h2 = h. Take the first n items from the .  Remove first n items from the .  n h: Return a list of the first n items of h and h, with  those elements removed.  p h&: List the longest prefix of items in h that satisfy p.   p h(: Remove the longest prefix of items in h that satisfy  p. !! p h(: Return the longest prefix of items in h that satisfy p and  h, with those elements removed. "" p h!: The longest prefix of items in h that do not satisfy p  and h, with those elements removed. # O(n log n) . Build a + from the given items. Assuming you have a ' sorted list, you probably want to use ' or %, they  are faster than this function. $ O(n log n). List all items of the  in no specific order. %O(n) . Create a 4 from a list providing its items in ascending order D of priority (i. e. in the same order they will be removed from the ).  This function is faster than # but not as fast as '. The precondition is not checked. & O(n log n). List the items of the ! in ascending order of priority. 'O(n) . Create a 5 from a list providing its items in descending order < of priority (i. e. they will be removed inversely from the  ). Prefer  this function over # and %, it' s faster. The precondition is not checked. ( O(n log n). List the items of the " in descending order of priority. K Note that this function is not especially efficient (it is implemented in  terms of D and &*), it is provided as a counterpart of the  efficient ' function. )  !"#$%&'()   !"#$%&'( !"#$%&'(E      !"#$%&'()*+,-./0123456789:"%'(+*;8<=8<>8<?8@AB8CDE heap-1.0.0 Data.HeapData.Heap.InternalData.Heap.ItemHeapTisEmptysizeemptyunionunions FstMaxPolicy FstMinPolicy MaxPolicy MinPolicyHeapItemPrioValsplitmerge MaxPrioHeap MinPrioHeapMaxHeapMinHeapHeapnull singletoninsertviewviewHeadviewTailfilter partitiontakedropsplitAt takeWhile dropWhilespanbreakfromListtoList fromAscList toAscList fromDescList toDescListTree_rank_size _priority_value_left_rightEmptyrank uncheckedConsmakeTbase Data.MaybeNothing toPairAscList GHC.ClassesOrdEqcompare Data.TuplefstsplitFGHC.Listreverse