General-purpose heap. More...

#include <w_heap.h>

Public Member Functions
	Heap (const Cmp &cmpFunction, int initialNumElements=32)

	~Heap ()

int	NumElements () const
	How many elements in the heap? More...

T	RemoveFirst ()
	Take top/largest element off. More...

T	RemoveN (int i)
	Remove element from the middle. More...

void	AddElement (const T &elem)
	Put in heap and recompute to restore heap property. More...

void	AddElementDontHeapify (const T &elem)
	Put in heap but do NOT recompute to restore heap property. More...

void	Heapify ()
	Recompute to restore heap property. More...

T &	First ()
	Get reference to top of heap (do not remove) More...

T &	Value (int i)
	Get reference arbitrary element (do not remove) More...

const T &	Second () const
	Get reference element just below top (do not remove) More...

void	ReplacedFirst ()
	Inform heap that I replaced the top: recompute, but more efficient than Heapify() More...

void	IncreasedN (int i)
	Inform heap that element i must rise in heap to restore heap property. More efficient than general Heapify() More...

void	DecreasedN (int i)
	Inform heap that element i must drop in heap to restore heap property. More efficient than general Heapify() More...

void	CheckHeap () const
	Check heap property. More...

void	Print (ostream &out) const
	Dump heap. More...

bool	HeapProperty (int root) const
	Check heap property from given root to the bottom. More...

Protected Member Functions
int	LeftChild (int i) const

int	RightChild (int i) const

int	RightSibling (int i) const

int	Parent (int i) const

void	PrintRoot (ostream &out, int rootElem, int indentLevel) const

void	CheckHeapRoot (int rootElem) const

bool	HeapProperty (int lower, int upper) const

void	SiftDown (int rootElem)

void	SiftUp (int rootElem)

void	GrowElements (int newSize)

Protected Attributes
int	numElements

int	maxNumElements

T *	elements

const Cmp &	cmp

Detailed Description

template<class T, class Cmp>
class Heap< T, Cmp >

General-purpose heap.

This class implements a general purpose heap. The element type T and the ordering function (via class Cmp) are passed in as parameters to the Heap template.

This heap sifts the LARGEST elements to the top and the SMALLEST elements to the bottom, according tho the comparison function, Cmp.gt(). Thus the "heap property" is that value(Parent(i)) gt value(i) for each element i in the heap.

An element anywhere in the heap can be changed (by an outsider- not by the heap template) and the heap property can be restored, but he who changes the element must know whether the element's key value increased or decreased. Since we're sifting "large" elements to the top of the heap, if the element's key value increases, the element must be sifted UP, and if its value decreases, it must be sifted down. The methods IncreaseN and DecreaseN handle these cases.

The heap has the following worst case run times:

create initial heap O(n)
retrieve first element O(1)
retrieve second element O(1)
replace first element O(log n)
delete first element O(log n)
add new element O(log n)
increment/decrement key for any element O(log n)

The comparison class, Cmp, must have the member functions gt (T* left, T* right) returns true iff left > right

RemoveFirst always removes the largest element.

Constructor & Destructor Documentation

§ Heap()

template<class T , class Cmp>

Heap< T, Cmp >::Heap	(	const Cmp &	cmpFunction,
		int	initialNumElements = `32`
	)

§ ~Heap()

template<class T , class Cmp >

Heap< T, Cmp >::~Heap ( )

Member Function Documentation

§ AddElement()

template<class T, class Cmp >

void Heap< T, Cmp >::AddElement ( const T & elem )

Put in heap and recompute to restore heap property.

§ AddElementDontHeapify()

template<class T, class Cmp >

void Heap< T, Cmp >::AddElementDontHeapify ( const T & elem )

Put in heap but do NOT recompute to restore heap property.

§ CheckHeap()

template<class T , class Cmp >

void Heap< T, Cmp >::CheckHeap ( ) const

inline

Check heap property.

§ CheckHeapRoot()

template<class T , class Cmp >

void Heap< T, Cmp >::CheckHeapRoot ( int rootElem ) const

protected

§ DecreasedN()

template<class T , class Cmp >

void Heap< T, Cmp >::DecreasedN ( int i )

inline

Inform heap that element i must drop in heap to restore heap property. More efficient than general Heapify()

§ First()

template<class T , class Cmp >

T & Heap< T, Cmp >::First ( )

Get reference to top of heap (do not remove)

§ GrowElements()

template<class T , class Cmp >

void Heap< T, Cmp >::GrowElements ( int newSize )

protected

§ Heapify()

template<class T , class Cmp >

void Heap< T, Cmp >::Heapify ( )

Recompute to restore heap property.

§ HeapProperty() [1/2]

template<class T , class Cmp >

bool Heap< T, Cmp >::HeapProperty ( int root ) const

Check heap property from given root to the bottom.

§ HeapProperty() [2/2]

template<class T , class Cmp >

bool Heap< T, Cmp >::HeapProperty	(	int	lower,
		int	upper
	)		const

protected

§ IncreasedN()

template<class T , class Cmp >

void Heap< T, Cmp >::IncreasedN ( int i )

inline

Inform heap that element i must rise in heap to restore heap property. More efficient than general Heapify()

§ LeftChild()

template<class T , class Cmp >

int Heap< T, Cmp >::LeftChild ( int i ) const

inlineprotected

§ NumElements()

template<class T , class Cmp >

int Heap< T, Cmp >::NumElements ( ) const

inline

How many elements in the heap?

§ Parent()

template<class T , class Cmp >

int Heap< T, Cmp >::Parent ( int i ) const

inlineprotected

§ Print()

template<class T , class Cmp >

void Heap< T, Cmp >::Print ( ostream & out ) const

inline

Dump heap.

§ PrintRoot()

template<class T , class Cmp >

void Heap< T, Cmp >::PrintRoot	(	ostream &	out,
		int	rootElem,
		int	indentLevel
	)		const

protected

§ RemoveFirst()

template<class T , class Cmp >

T Heap< T, Cmp >::RemoveFirst ( )

Take top/largest element off.

§ RemoveN()

template<class T , class Cmp >

T Heap< T, Cmp >::RemoveN ( int i )

Remove element from the middle.

§ ReplacedFirst()

template<class T , class Cmp >

void Heap< T, Cmp >::ReplacedFirst ( )

inline

Inform heap that I replaced the top: recompute, but more efficient than Heapify()

§ RightChild()

template<class T , class Cmp >

int Heap< T, Cmp >::RightChild ( int i ) const

inlineprotected

§ RightSibling()

template<class T , class Cmp >

int Heap< T, Cmp >::RightSibling ( int i ) const

inlineprotected

§ Second()

template<class T , class Cmp >

const T & Heap< T, Cmp >::Second ( ) const

Get reference element just below top (do not remove)

§ SiftDown()

template<class T , class Cmp >

void Heap< T, Cmp >::SiftDown ( int rootElem )

protected

§ SiftUp()

template<class T , class Cmp >

void Heap< T, Cmp >::SiftUp ( int rootElem )

protected

§ Value()

template<class T , class Cmp >

T & Heap< T, Cmp >::Value ( int i )

Get reference arbitrary element (do not remove)

Member Data Documentation

§ cmp

template<class T, class Cmp>

const Cmp& Heap< T, Cmp >::cmp

protected

§ elements

template<class T, class Cmp>

T* Heap< T, Cmp >::elements

protected

§ maxNumElements

template<class T, class Cmp>

int Heap< T, Cmp >::maxNumElements

protected

§ numElements

template<class T, class Cmp>

int Heap< T, Cmp >::numElements

protected

The documentation for this class was generated from the following file:

src/common/w_heap.h

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class T, class Cmp> class Heap< T, Cmp >

Constructor & Destructor Documentation

§ Heap()

§ ~Heap()

Member Function Documentation

§ AddElement()

§ AddElementDontHeapify()

§ CheckHeap()

§ CheckHeapRoot()

§ DecreasedN()

§ First()

§ GrowElements()

§ Heapify()

§ HeapProperty() [1/2]

§ HeapProperty() [2/2]

§ IncreasedN()

§ LeftChild()

§ NumElements()

§ Parent()

§ Print()

§ PrintRoot()

§ RemoveFirst()

§ RemoveN()

§ ReplacedFirst()

§ RightChild()

§ RightSibling()

§ Second()

§ SiftDown()

§ SiftUp()

§ Value()

Member Data Documentation

§ cmp

§ elements

§ maxNumElements

§ numElements

template<class T, class Cmp>
class Heap< T, Cmp >