`Data.Heap.Binary`

provides a binary min-heap. Balance is maintained through descendant counting.

- data Ord n => BinaryHeap n
- head :: Ord a => BinaryHeap a -> a
- tail :: Ord a => BinaryHeap a -> BinaryHeap a
- merge :: Ord a => BinaryHeap a -> BinaryHeap a -> BinaryHeap a
- singleton :: Ord a => a -> BinaryHeap a
- empty :: Ord a => BinaryHeap a
- null :: Ord a => BinaryHeap a -> Bool
- fromList :: Ord a => [a] -> BinaryHeap a
- toList :: Ord a => BinaryHeap a -> [a]
- insert :: Ord a => a -> BinaryHeap a -> BinaryHeap a

# Documentation

data Ord n => BinaryHeap n Source

Ord n => Eq (BinaryHeap n) | |

Ord n => Ord (BinaryHeap n) | |

(Ord n, Show n) => Show (BinaryHeap n) |

head :: Ord a => BinaryHeap a -> aSource

*O(1)*. `head`

returns the element root of the heap.

tail :: Ord a => BinaryHeap a -> BinaryHeap aSource

*O(lg n)*. `tail`

discards the root of the heap and merges the subtrees.

merge :: Ord a => BinaryHeap a -> BinaryHeap a -> BinaryHeap aSource

`merge`

consumes two binary heaps and merges them.

singleton :: Ord a => a -> BinaryHeap aSource

*O(1)*. `singleton`

consumes an element and constructs a singleton heap.

empty :: Ord a => BinaryHeap aSource

*O(1)*. `empty`

produces an empty heap.

null :: Ord a => BinaryHeap a -> BoolSource

*O(1)*.

fromList :: Ord a => [a] -> BinaryHeap aSource

*O(n)*. `fromList`

constructs a binary heap from an unsorted list.

toList :: Ord a => BinaryHeap a -> [a]Source

*O(n lg n)*.

insert :: Ord a => a -> BinaryHeap a -> BinaryHeap aSource

*O(lg n)*.