-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Heaps in Haskell
--
-- A flexible Haskell heap implementation
@package heap
@version 0.1
-- | An efficent 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.
deleteHead :: (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
-- | 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 it's 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) => 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)