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


-- | Tree structures
--   
--   A collection of heaps and search trees
@package TreeStructures
@version 0.0.1

module Data.Tree.Splay
data (Ord k) => SplayTree k v

-- | <i>O(1)</i>. <a>head</a> returns the key-value pair of the root.
head :: (Ord k) => SplayTree k v -> (k, v)

-- | <i>Amortized O(lg n)</i>. <a>tail</a> removes the root of the tree and
--   merges its subtrees
tail :: (Ord k) => SplayTree k v -> SplayTree k v

-- | <i>O(1)</i>. <a>singleton</a> constructs a splay tree containing one
--   element.
singleton :: (Ord k) => (k, v) -> SplayTree k v

-- | <i>O(1)</i>. <a>empty</a> constructs an empty splay tree.
empty :: (Ord k) => SplayTree k v

-- | <i>O(1)</i>. <a>null</a> returns true if a splay tree is empty.
null :: (Ord k) => SplayTree k v -> Bool

-- | <i>O(n lg n)</i>. Constructs a splay tree from an unsorted list of
--   key-value pairs.
fromList :: (Ord k) => [(k, v)] -> SplayTree k v

-- | <i>O(n lg n)</i>. Constructs a splay tree from a list of key-value
--   pairs sorted in ascending order.
fromAscList :: (Ord k) => [(k, v)] -> SplayTree k v

-- | <i>O(n lg n)</i>. Converts a splay tree into a list of key-value pairs
--   with no constraint on ordering.
toList :: (Ord k) => SplayTree k v -> [(k, v)]

-- | <i>O(n lg n)</i>. <a>toAscList</a> converts a splay tree to a list of
--   key-value pairs sorted in ascending order.
toAscList :: (Ord k) => SplayTree k v -> [(k, v)]

-- | <i>Amortized O(lg n)</i>. Given a splay tree and a key-value pair,
--   <a>insert</a> places the the pair into the tree in BST order.
insert :: (Ord k) => SplayTree k v -> (k, v) -> SplayTree k v

-- | <i>Amortized O(lg n)</i>. Given a splay tree and a key, <a>lookup</a>
--   attempts to find a node with the specified key and splays this node to
--   the root. If the key is not found, the nearest node is brought to the
--   root of the tree.
lookup :: (Ord k) => SplayTree k v -> k -> SplayTree k v
instance (Ord k, Ord v) => Ord (SplayTree k v)
instance (Eq v, Ord k) => Eq (SplayTree k v)

module Data.Heap.Skew
data (Ord a) => SkewHeap a
head :: (Ord a) => SkewHeap a -> a
tail :: (Ord a) => SkewHeap a -> SkewHeap a
merge :: (Ord a) => SkewHeap a -> SkewHeap a -> SkewHeap a
singleton :: (Ord a) => a -> SkewHeap a
empty :: (Ord a) => SkewHeap a
null :: (Ord a) => SkewHeap a -> Bool
fromList :: (Ord a) => [a] -> SkewHeap a
toList :: (Ord a) => SkewHeap a -> [a]
insert :: (Ord a) => SkewHeap a -> a -> SkewHeap a
instance (Ord a) => Eq (SkewHeap a)
instance (Ord a) => Ord (SkewHeap a)

module Data.Heap.Binomial
data (Ord a, Eq a) => BinomialHeap a

-- | <i>O(lg n)</i>
head :: (Ord a) => BinomialHeap a -> a

-- | <i>O(lg n)</i>
tail :: (Ord a) => BinomialHeap a -> BinomialHeap a

-- | <i>O(lg n)</i>.
merge :: (Ord a) => BinomialHeap a -> BinomialHeap a -> BinomialHeap a

-- | <i>O(1)</i>.
singleton :: (Ord a) => a -> BinomialHeap a
empty :: (Ord a) => BinomialHeap a
null :: (Ord a) => BinomialHeap a -> Bool

-- | <i>O(n)</i>
fromList :: (Ord a, Eq a) => [a] -> BinomialHeap a

-- | <i>O(n lg n)</i>
toList :: (Ord a) => BinomialHeap a -> [a]

-- | <i>O(lg n)</i>
insert :: (Ord a) => BinomialHeap a -> a -> BinomialHeap a
instance (Ord a) => Eq (BinomialHeap a)
instance (Ord a) => Ord (BinomialHeap a)
instance (Ord a, Ord b, Eq a, Eq b) => Eq (HeapNode a b)
instance (Ord a, Ord b, Eq a, Eq b) => Ord (HeapNode a b)


-- | <tt>Data.Heap.Binary</tt> provides a binary min-heap. Balance is
--   maintained through descendant counting.
module Data.Heap.Binary
data (Ord n) => BinaryHeap n

-- | <i>O(1)</i>. <a>head</a> returns the element root of the heap.
head :: (Ord a) => BinaryHeap a -> a

-- | <i>O(lg n)</i>. <a>tail</a> discards the root of the heap and merges
--   the subtrees.
tail :: (Ord a) => BinaryHeap a -> BinaryHeap a

-- | <a>merge</a> consumes two binary heaps and merges them.
merge :: (Ord a) => BinaryHeap a -> BinaryHeap a -> BinaryHeap a

-- | <i>O(1)</i>. <a>singleton</a> consumes an element and constructs a
--   singleton heap.
singleton :: (Ord a) => a -> BinaryHeap a

-- | <i>O(1)</i>. <a>empty</a> produces an empty heap.
empty :: (Ord a) => BinaryHeap a

-- | <i>O(1)</i>.
null :: (Ord a) => BinaryHeap a -> Bool

-- | <i>O(n)</i>. <a>fromList</a> constructs a binary heap from an unsorted
--   list.
fromList :: (Ord a) => [a] -> BinaryHeap a

-- | <i>O(n lg n)</i>.
toList :: (Ord a) => BinaryHeap a -> [a]

-- | <i>O(lg n)</i>.
insert :: (Ord a) => BinaryHeap a -> a -> BinaryHeap a
instance (Ord n) => Eq (BinaryHeap n)
instance (Ord n) => Ord (BinaryHeap n)
instance (Ord n, Show n) => Show (BinaryHeap n)