Data.Heap.Binary

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

Documentation

data Ord n => BinaryHeap n

Instances

Ord n => Eq (BinaryHeap n)

Ord n => Ord (BinaryHeap n)

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

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

O(1). head returns the element root of the heap.

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

O(lg n). tail discards the root of the heap and merges the subtrees.

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

merge consumes two binary heaps and merges them.

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

O(1). singleton consumes an element and constructs a singleton heap.

empty :: Ord a => BinaryHeap a

O(1). empty produces an empty heap.

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

O(1).

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

O(n). fromList constructs a binary heap from an unsorted list.

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

O(n lg n).

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

O(lg n).