This class implements a heap data structure. More...

Inheritance diagram for grafalgo::DiffHeap:

Collaboration diagram for grafalgo::DiffHeap:

Public Member Functions
	DiffHeap (int, int)
	Constructor for DiffHeap class.
	~DiffHeap ()
	Destructor for DiffHeap class.
void	clear ()
	Remove all elements from heap.
void	resize (int)
	Resize a DiffHeap object.
void	expand (int)
	Expand the space available for this DiffHeap.
void	copyFrom (const DiffHeap &)
	Copy into DiffHeap from source.
index	findmin () const
	Find an item in the heap with the smallest key.
keytyp	key (index) const
	Get the key of item.
bool	member (index) const
	Determine if an item is in the heap.
bool	empty () const
	Determine if the heap is empty.
void	insert (index, keytyp)
	Add item to the heap.
void	remove (index)
	Remove an item from the heap.
index	deletemin ()
	Delete a minimum key item from the heap and return it.
void	changekey (index, keytyp)
	Change the key of an item in the heap.
void	addtokeys (keytyp)
void	clearStats ()
	Clear the statistics counters.
string &	stats2string (string &) const
	Return a string representation of the statistics counters.
string &	toString (string &) const
Private Member Functions
index	minchild (index)
	Find the position of the child withthe smallest key.
void	siftup (index, int)
void	siftdown (index, int)
	Perform siftdown operation to restore heap order.
void	makeSpace (int)
	Allocate and initialize space for DiffHeap.
void	freeSpace ()
	Free dynamic storage used by DiffHeap.
Private Attributes
int	hn
	number of items in the heap
index *	h
	{h[1],...,h[hn]} is set of items
int *	pos
	pos[i] gives position of i in h
keytyp *	dkey
	dkey[i] is delta-key of item i

Detailed Description

This class implements a heap data structure.

The heap elements are identified by index values in 1..n where n is specified when an object is constructed. This version uses a differential representation of the keys. This allows it to implement a constant time addtokeys() operation.

Definition at line 24 of file DiffHeap.cpp.

Constructor & Destructor Documentation

grafalgo::DiffHeap::DiffHeap	(	int	,
		int
	)

Constructor for DiffHeap class.

Parameters:

size	is the number of items in the contructed object
D1	is the degree of the underlying heap-ordered tree

Definition at line 21 of file DiffHeap.cpp.

Here is the call graph for this function:

grafalgo::DiffHeap::~DiffHeap ( )

Destructor for DiffHeap class.

Definition at line 26 of file DiffHeap.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::DiffHeap::changekey	(	index	i,
		keytyp	k
	)

Change the key of an item in the heap.

Parameters:

i	is the index of an item in the heap
k	is a new key value for item i

Definition at line 174 of file DiffHeap.cpp.

Here is the call graph for this function:

void grafalgo::DiffHeap::clear ( ) [virtual]

Remove all elements from heap.

Implements grafalgo::Adt.

Definition at line 84 of file DiffHeap.cpp.

Here is the caller graph for this function:

void grafalgo::DiffHeap::copyFrom ( const DiffHeap & source )

Copy into DiffHeap from source.

Definition at line 51 of file DiffHeap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int grafalgo::DiffHeap::deletemin ( ) [inline]

Delete a minimum key item from the heap and return it.

Returns:: the index an item of minimum key from the heap, after deleting it from the heap

Definition at line 78 of file DiffHeap.cpp.

bool grafalgo::DiffHeap::empty ( ) const [inline]

Determine if the heap is empty.

Returns:: true if heap is empty, else false

Definition at line 93 of file DiffHeap.cpp.

void grafalgo::DiffHeap::expand ( int size ) [virtual]

Expand the space available for this DiffHeap.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 77 of file DiffHeap.cpp.

Here is the call graph for this function:

int grafalgo::DiffHeap::findmin ( ) const [inline]

Find an item in the heap with the smallest key.

Returns:: the index of an item that has the smallest key

Definition at line 72 of file DiffHeap.cpp.

void grafalgo::DiffHeap::freeSpace ( ) [private]

Free dynamic storage used by DiffHeap.

Definition at line 48 of file DiffHeap.cpp.

Here is the caller graph for this function:

void grafalgo::DiffHeap::insert	(	index	i,
		keytyp	k
	)

Add item to the heap.

Parameters:

i	is the index of an item that is not in the heap
k	is the key value under which i is to be inserted

Definition at line 103 of file DiffHeap.cpp.

Here is the call graph for this function:

keytyp grafalgo::DiffHeap::key ( index i ) const [inline]

Get the key of item.

Parameters:

i	is the index of an item in the heap

Returns:: the value of i's key

Definition at line 93 of file DiffHeap.cpp.

Here is the caller graph for this function:

void grafalgo::DiffHeap::makeSpace ( int size ) [private]

Allocate and initialize space for DiffHeap.

Parameters:

size	is number of index values to provide space for

Definition at line 31 of file DiffHeap.cpp.

Here is the caller graph for this function:

bool grafalgo::DiffHeap::member ( index i ) const [inline]

Determine if an item is in the heap.

Parameters:

i	is the index of an item in the heap

Returns:: true if i is in the heap, else false

Definition at line 88 of file DiffHeap.cpp.

int grafalgo::DiffHeap::minchild ( index ) [private]

Find the position of the child withthe smallest key.

This is a private helper function, used by siftdown.

Parameters:

x	is a position of an item in the heap

Returns:: the position of the child of the item at x, that has the smallest key

Definition at line 144 of file Dheap.cpp.

Here is the caller graph for this function:

void grafalgo::DiffHeap::remove ( index i )

Remove an item from the heap.

Parameters:

i	is an item in the heap

Definition at line 110 of file DiffHeap.cpp.

Here is the call graph for this function:

void grafalgo::DiffHeap::resize ( int size ) [virtual]

Resize a DiffHeap object.

The old value is discarded.

Parameters:

size	is the size of the resize

Implements grafalgo::Adt.

Definition at line 65 of file DiffHeap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::DiffHeap::siftdown	(	index	i,
		int	x
	)		`[private]`

Perform siftdown operation to restore heap order.

This is a private helper function.

Parameters:

i	is an index to be positioned in the heap
x	is a tentative position for i in the heap

Definition at line 145 of file DiffHeap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::DiffHeap::stats2string ( string & ) const

Return a string representation of the statistics counters.

Parameters:

s	is a string in which the result is returned

Returns:: a reference to s

Definition at line 207 of file DiffHeap.cpp.

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

/Users/jst/src/grafalgo/cpp/include/DiffHeap.cpp
/Users/jst/src/grafalgo/cpp/dataStructures/heaps/Dheap.cpp
/Users/jst/src/grafalgo/cpp/dataStructures/heaps/DiffHeap.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation