-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Asymptotically optimal Brodal/Okasaki heaps.
--   
--   Asymptotically optimal Brodal/Okasaki bootstrapped skew-binomial heaps
--   from the paper <a>"Optimal Purely Functional Priority Queues"</a>,
--   extended with a <a>Foldable</a> interface.
@package heaps
@version 0.4.1


-- | An efficient, asymptotically optimal, implementation of a priority
--   queues extended with support for efficient size, and <a>Foldable</a>
--   
--   <i>Note</i>: Since many function names (but not the type name) clash
--   with <a>Prelude</a> names, this module is usually imported
--   <tt>qualified</tt>, e.g.
--   
--   <pre>
--   import Data.Heap (Heap)
--   import qualified Data.Heap as Heap
--   </pre>
--   
--   The implementation of <a>Heap</a> is based on <i>bootstrapped skew
--   binomial heaps</i> as described by:
--   
--   <ul>
--   <li>G. Brodal and C. Okasaki , <a>"Optimal Purely Functional Priority
--   Queues"</a>, <i>Journal of Functional Programming</i> 6:839-857
--   (1996)</li>
--   </ul>
--   
--   All time bounds are worst-case.
module Data.Heap

-- | A min-heap of values of type <tt>a</tt>.
data Heap a

-- | Explicit priority/payload tuples. Useful to build a priority queue
--   using a <a>Heap</a>, since the payload is ignored in the Eq/Ord
--   instances.
--   
--   <pre>
--   myHeap = <a>fromList</a> [<a>Entry</a> 2 "World", <a>Entry</a> 1 "Hello", <a>Entry</a> 3 "!"]
--   
--   ==&gt; <a>foldMap</a> <a>payload</a> myHeap ≡ "HelloWorld!"
--   </pre>
data Entry p a
Entry :: p -> a -> Entry p a
[priority] :: Entry p a -> p
[payload] :: Entry p a -> a

-- | <i>O(1)</i>. The empty heap
--   
--   <pre>
--   <a>empty</a> ≡ <a>fromList</a> []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; size empty
--   0
--   </pre>
empty :: Heap a

-- | <i>O(1)</i>. Is the heap empty?
--   
--   <pre>
--   &gt;&gt;&gt; null empty
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; null (singleton "hello")
--   False
--   </pre>
null :: Heap a -> Bool

-- | <i>O(1)</i>. The number of elements in the heap.
--   
--   <pre>
--   &gt;&gt;&gt; size empty
--   0
--   
--   &gt;&gt;&gt; size (singleton "hello")
--   1
--   
--   &gt;&gt;&gt; size (fromList [4,1,2])
--   3
--   </pre>
size :: Heap a -> Int

-- | <i>O(1)</i>. A heap with a single element
--   
--   <pre>
--   <a>singleton</a> x ≡ <a>fromList</a> [x]
--   <a>singleton</a> x ≡ <a>insert</a> x <a>empty</a>
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; size (singleton "hello")
--   1
--   </pre>
singleton :: Ord a => a -> Heap a

-- | <i>O(1)</i>. Insert a new value into the heap.
--   
--   <pre>
--   &gt;&gt;&gt; insert 2 (fromList [1,3])
--   fromList [1,2,3]
--   </pre>
--   
--   <pre>
--   <a>insert</a> x <a>empty</a> ≡ <a>singleton</a> x
--   <a>size</a> (<a>insert</a> x xs) ≡ 1 + <a>size</a> xs
--   </pre>
insert :: Ord a => a -> Heap a -> Heap a

-- | <i>O(1)</i>. Assumes the argument is a non-<a>null</a> heap.
--   
--   <pre>
--   &gt;&gt;&gt; minimum (fromList [3,1,2])
--   1
--   </pre>
minimum :: Heap a -> a

-- | <i>O(log n)</i>. Delete the minimum key from the heap and return the
--   resulting heap.
--   
--   <pre>
--   &gt;&gt;&gt; deleteMin (fromList [3,1,2])
--   fromList [2,3]
--   </pre>
deleteMin :: Heap a -> Heap a

-- | <i>O(log n)</i>. Adjust the minimum key in the heap and return the
--   resulting heap.
--   
--   <pre>
--   &gt;&gt;&gt; adjustMin (+1) (fromList [1,2,3])
--   fromList [2,2,3]
--   </pre>
adjustMin :: (a -> a) -> Heap a -> Heap a

-- | <i>O(1)</i>. Meld the values from two heaps into one heap.
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [1,3,5]) (fromList [6,4,2])
--   fromList [1,2,6,4,3,5]
--   
--   &gt;&gt;&gt; union (fromList [1,1,1]) (fromList [1,2,1])
--   fromList [1,1,1,2,1,1]
--   </pre>
union :: Heap a -> Heap a -> Heap a

-- | Provides both <i>O(1)</i> access to the minimum element and <i>O(log
--   n)</i> access to the remainder of the heap. This is the same operation
--   as <a>viewMin</a>
--   
--   <pre>
--   &gt;&gt;&gt; uncons (fromList [2,1,3])
--   Just (1,fromList [2,3])
--   </pre>
uncons :: Heap a -> Maybe (a, Heap a)

-- | Same as <a>uncons</a>
viewMin :: Heap a -> Maybe (a, Heap a)

-- | <i>O(n)</i>. Map a monotone increasing function over the heap.
--   Provides a better constant factor for performance than <a>map</a>, but
--   no checking is performed that the function provided is monotone
--   increasing. Misuse of this function can cause a Heap to violate the
--   heap property.
--   
--   <pre>
--   &gt;&gt;&gt; mapMonotonic (+1) (fromList [1,2,3])
--   fromList [2,3,4]
--   
--   &gt;&gt;&gt; mapMonotonic (*2) (fromList [1,2,3])
--   fromList [2,4,6]
--   </pre>
mapMonotonic :: Ord b => (a -> b) -> Heap a -> Heap b

-- | <i>O(n)</i>. Map a function over the heap, returning a new heap
--   ordered appropriately for its fresh contents
--   
--   <pre>
--   &gt;&gt;&gt; map negate (fromList [3,1,2])
--   fromList [-3,-1,-2]
--   </pre>
map :: Ord b => (a -> b) -> Heap a -> Heap b

-- | <i>O(n)</i>. Returns the elements in the heap in some arbitrary, very
--   likely unsorted, order.
--   
--   <pre>
--   &gt;&gt;&gt; toUnsortedList (fromList [3,1,2])
--   [1,3,2]
--   </pre>
--   
--   <pre>
--   <a>fromList</a> <a>.</a> <a>toUnsortedList</a> ≡ <a>id</a>
--   </pre>
toUnsortedList :: Heap a -> [a]

-- | <i>O(n)</i>. Build a heap from a list of values.
--   
--   <pre>
--   <a>fromList</a> <a>.</a> <tt>toList</tt> ≡ <a>id</a>
--   <tt>toList</tt> <a>.</a> <a>fromList</a> ≡ <a>sort</a>
--   </pre>
fromList :: Ord a => [a] -> Heap a

-- | <i>O(n log n)</i>. Perform a heap sort
sort :: Ord a => [a] -> [a]

-- | <i>O(n log n)</i>. Traverse the elements of the heap in sorted order
--   and produce a new heap using <a>Applicative</a> side-effects.
traverse :: (Applicative t, Ord b) => (a -> t b) -> Heap a -> t (Heap b)

-- | <i>O(n log n)</i>. Traverse the elements of the heap in sorted order
--   and produce a new heap using <a>Monad</a>ic side-effects.
mapM :: (Monad m, Ord b) => (a -> m b) -> Heap a -> m (Heap b)

-- | <i>O(n)</i>. Construct heaps from each element in another heap, and
--   union them together.
--   
--   <pre>
--   &gt;&gt;&gt; concatMap (\a -&gt; fromList [a,a+1]) (fromList [1,4])
--   fromList [1,4,5,2]
--   </pre>
concatMap :: (a -> Heap b) -> Heap a -> Heap b

-- | <i>O(n)</i>. Filter the heap, retaining only values that satisfy the
--   predicate.
--   
--   <pre>
--   &gt;&gt;&gt; filter (&gt;'a') (fromList "ab")
--   fromList "b"
--   
--   &gt;&gt;&gt; filter (&gt;'x') (fromList "ab")
--   fromList []
--   
--   &gt;&gt;&gt; filter (&lt;'a') (fromList "ab")
--   fromList []
--   </pre>
filter :: (a -> Bool) -> Heap a -> Heap a

-- | <i>O(n)</i>. Partition the heap according to a predicate. The first
--   heap contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
--   
--   <pre>
--   &gt;&gt;&gt; partition (&gt;'a') (fromList "ab")
--   (fromList "b",fromList "a")
--   </pre>
partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a)

-- | <i>O(n)</i>. Partition the heap into heaps of the elements that are
--   less than, equal to, and greater than a given value.
--   
--   <pre>
--   &gt;&gt;&gt; split 'h' (fromList "hello")
--   (fromList "e",fromList "h",fromList "llo")
--   </pre>
split :: a -> Heap a -> (Heap a, Heap a, Heap a)

-- | <i>O(n log n)</i>. <a>break</a> applied to a predicate <tt>p</tt> and
--   a heap <tt>xs</tt> returns a tuple where the first element is a heap
--   consisting of the longest prefix the least elements of <tt>xs</tt>
--   that <i>do not satisfy</i> p and the second element is the remainder
--   of the elements in the heap.
--   
--   <pre>
--   &gt;&gt;&gt; break (\x -&gt; x `mod` 4 == 0) (fromList [3,5,7,12,13,16])
--   (fromList [3,5,7],fromList [12,13,16])
--   </pre>
--   
--   <a>break</a> <tt>p</tt> is equivalent to <tt><a>span</a> (<a>not</a> .
--   p)</tt>.
break :: (a -> Bool) -> Heap a -> (Heap a, Heap a)

-- | <i>O(n log n)</i>. <a>span</a> applied to a predicate <tt>p</tt> and a
--   heap <tt>xs</tt> returns a tuple where the first element is a heap
--   consisting of the longest prefix the least elements of xs that satisfy
--   <tt>p</tt> and the second element is the remainder of the elements in
--   the heap.
--   
--   <pre>
--   &gt;&gt;&gt; span (\x -&gt; x `mod` 4 == 0) (fromList [4,8,12,14,16])
--   (fromList [4,8,12],fromList [14,16])
--   </pre>
--   
--   <a>span</a> <tt>p xs</tt> is equivalent to <tt>(<a>takeWhile</a> p xs,
--   <a>dropWhile</a> p xs)</tt>
span :: (a -> Bool) -> Heap a -> (Heap a, Heap a)

-- | <i>O(n log n)</i>. Return a heap consisting of the least <tt>n</tt>
--   elements of a given heap.
--   
--   <pre>
--   &gt;&gt;&gt; take 3 (fromList [10,2,4,1,9,8,2])
--   fromList [1,2,2]
--   </pre>
take :: Int -> Heap a -> Heap a

-- | <i>O(n log n)</i>. Return a heap consisting of all members of given
--   heap except for the <tt>n</tt> least elements.
drop :: Int -> Heap a -> Heap a

-- | <i>O(n log n)</i>. Split a heap into two heaps, the first containing
--   the <tt>n</tt> least elements, the latter consisting of all members of
--   the heap except for those elements.
splitAt :: Int -> Heap a -> (Heap a, Heap a)

-- | <i>O(n log n)</i>. <a>takeWhile</a> applied to a predicate <tt>p</tt>
--   and a heap <tt>xs</tt> returns a heap consisting of the longest prefix
--   the least elements of <tt>xs</tt> that satisfy <tt>p</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; takeWhile (\x -&gt; x `mod` 4 == 0) (fromList [4,8,12,14,16])
--   fromList [4,8,12]
--   </pre>
takeWhile :: (a -> Bool) -> Heap a -> Heap a

-- | <i>O(n log n)</i>. <a>dropWhile</a> <tt>p xs</tt> returns the suffix
--   of the heap remaining after <a>takeWhile</a> <tt>p xs</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; dropWhile (\x -&gt; x `mod` 4 == 0) (fromList [4,8,12,14,16])
--   fromList [14,16]
--   </pre>
dropWhile :: (a -> Bool) -> Heap a -> Heap a

-- | <i>O(n log n)</i>. Group a heap into a heap of heaps, by unioning
--   together duplicates.
--   
--   <pre>
--   &gt;&gt;&gt; group (fromList "hello")
--   fromList [fromList "e",fromList "h",fromList "ll",fromList "o"]
--   </pre>
group :: Heap a -> Heap (Heap a)

-- | <i>O(n log n)</i>. Group using a user supplied function.
groupBy :: (a -> a -> Bool) -> Heap a -> Heap (Heap a)

-- | <i>O(n log n)</i>. Remove duplicate entries from the heap.
--   
--   <pre>
--   &gt;&gt;&gt; nub (fromList [1,1,2,6,6])
--   fromList [1,2,6]
--   </pre>
nub :: Heap a -> Heap a

-- | <i>O(n log n + m log m)</i>. Intersect the values in two heaps,
--   returning the value in the left heap that compares as equal
intersect :: Heap a -> Heap a -> Heap a

-- | <i>O(n log n + m log m)</i>. Intersect the values in two heaps using a
--   function to generate the elements in the right heap.
intersectWith :: Ord b => (a -> a -> b) -> Heap a -> Heap a -> Heap b

-- | <i>O(log n)</i>. Create a heap consisting of multiple copies of the
--   same value.
--   
--   <pre>
--   &gt;&gt;&gt; replicate 'a' 10
--   fromList "aaaaaaaaaa"
--   </pre>
replicate :: Ord a => a -> Int -> Heap a
instance Data.Bifunctor.Bifunctor Data.Heap.Entry
instance (GHC.Internal.Data.Data.Data p, GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Data.Heap.Entry p a)
instance (GHC.Classes.Ord a, GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Data.Heap.Heap a)
instance GHC.Classes.Eq p => GHC.Classes.Eq (Data.Heap.Entry p a)
instance GHC.Classes.Eq (Data.Heap.Heap a)
instance GHC.Internal.Data.Foldable.Foldable (Data.Heap.Entry p)
instance GHC.Internal.Data.Foldable.Foldable Data.Heap.Forest
instance GHC.Internal.Data.Foldable.Foldable Data.Heap.Heap
instance GHC.Internal.Data.Foldable.Foldable Data.Heap.Tree
instance GHC.Internal.Base.Functor (Data.Heap.Entry p)
instance GHC.Internal.Base.Functor Data.Heap.Forest
instance GHC.Internal.Base.Functor Data.Heap.Tree
instance GHC.Internal.Base.Monoid (Data.Heap.Heap a)
instance GHC.Classes.Ord p => GHC.Classes.Ord (Data.Heap.Entry p a)
instance GHC.Classes.Ord (Data.Heap.Heap a)
instance (GHC.Internal.Read.Read p, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Data.Heap.Entry p a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Heap.Forest a)
instance (GHC.Classes.Ord a, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Data.Heap.Heap a)
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Heap.Tree a)
instance GHC.Internal.Base.Semigroup (Data.Heap.Heap a)
instance (GHC.Internal.Show.Show p, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Data.Heap.Entry p a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Heap.Forest a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Heap.Heap a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Heap.Tree a)
instance GHC.Internal.Data.Traversable.Traversable (Data.Heap.Entry p)
