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

#include <Dheap.h>

Inheritance diagram for grafalgo::Dheap:

Collaboration diagram for grafalgo::Dheap:

Public Member Functions
	Dheap (int, int)
	Constructor for Dheap class.
	~Dheap ()
	Destructor for Dheap class.
void	clear ()
	Remove all elements from heap.
void	resize (int)
	Resize a Dheap object.
void	expand (int)
	Expand the space available for this Dheap.
void	copyFrom (const Dheap &)
	Copy into Dheap 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.
int	size () const
	Return size of heap.
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.
string &	toString (string &) const
	Construct a string representation of this object.
Private Member Functions
index	minchild (index)
void	siftup (index, int)
	Perform siftup operation to restore heap order.
void	siftdown (index, int)
	Perform siftdown operation to restore heap order.
void	makeSpace (int)
	Allocate and initialize space for Dheap.
void	freeSpace ()
	Free dynamic storage used by Dheap.
Private Attributes
int	d
	base of heap
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 *	kee
	kee[i] is key of item i

Detailed Description

This class implements a heap data structure.

The heap elements are identified by integers in 1..n where n is specified when an object is constructed.

Definition at line 23 of file Dheap.h.

Constructor & Destructor Documentation

grafalgo::Dheap::Dheap	(	int	size,
		int	dd
	)

Constructor for Dheap 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 Dheap.cpp.

Here is the call graph for this function:

grafalgo::Dheap::~Dheap ( )

Destructor for Dheap class.

Definition at line 26 of file Dheap.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::Dheap::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 157 of file Dheap.cpp.

Here is the call graph for this function:

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

Remove all elements from heap.

Implements grafalgo::Adt.

Definition at line 85 of file Dheap.cpp.

Here is the caller graph for this function:

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

Copy into Dheap from source.

Definition at line 51 of file Dheap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int grafalgo::Dheap::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 74 of file Dheap.h.

Here is the caller graph for this function:

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

Determine if the heap is empty.

Returns:: true if heap is empty, else false

Definition at line 95 of file Dheap.h.

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

Expand the space available for this Dheap.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 78 of file Dheap.cpp.

Here is the call graph for this function:

int grafalgo::Dheap::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 68 of file Dheap.h.

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

Free dynamic storage used by Dheap.

Definition at line 48 of file Dheap.cpp.

Here is the caller graph for this function:

void grafalgo::Dheap::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 94 of file Dheap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

keytyp grafalgo::Dheap::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 84 of file Dheap.h.

Here is the caller graph for this function:

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

Allocate and initialize space for Dheap.

Parameters:

size	is number of index values to provide space for

Definition at line 31 of file Dheap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::Dheap::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 90 of file Dheap.h.

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

Remove an item from the heap.

Parameters:

i	is an item in the heap

Definition at line 101 of file Dheap.cpp.

Here is the call graph for this function:

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

Resize a Dheap object.

The old value is discarded.

Parameters:

size	is the size of the resize

Implements grafalgo::Adt.

Definition at line 66 of file Dheap.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Dheap::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 129 of file Dheap.cpp.

Here is the caller graph for this function:

void grafalgo::Dheap::siftup	(	index	i,
		int	x
	)		`[private]`

Perform siftup operation to restore heap order.

This is a private helper function.

Parameters:

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

Definition at line 115 of file Dheap.cpp.

Here is the caller graph for this function:

string & grafalgo::Dheap::toString ( string & s ) const [virtual]

Construct a string representation of this object.

Parameters:

s	is a string in which the result is returned

Returns:: a reference to s

Implements grafalgo::Adt.

Definition at line 168 of file Dheap.cpp.

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

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation