TreeStructures-0.0.1: Tree structures

Data.Heap.Binary

Description

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

Synopsis

Documentation

data Ord n => BinaryHeap n Source

Instances

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 => BinaryHeap a -> a -> BinaryHeap aSource

O(lg n).