oofem::Heap Class Reference

#include <heap.h>

Public Member Functions
	Heap (int N)
	Constructor and destructor.
	~Heap ()
void	setToEmpty (int N)
	Interface with external algorithms (such as fast marching).
bool	isInHeap (int Ind)
int	nElems ()
void	insert (double time, int Ind)
void	update (double time, int Ind)
double	getSmallest (int *Ind)
int	checkHeapProperty (int pInd)
	Debugging tools.
void	print ()
void	printTree ()
double *	formMatrix (int m, int n)

Public Attributes
double *	Keys
int *	H2T
int *	T2H

Private Member Functions
void	upHeap (int Ind)
	Elementary heap operations.
void	downHeap (int Ind)
void	swapElements (int Ind1, int Ind2)
int	parentInd (int inInd)
	Index calculations.
int	leftChildInd (int inInd)
int	rightChildInd (int inInd)
int	lastParentInd ()
void	recurse (int row, int pad, int spacing, int S)
	Used by printTree. Does the actual printing, top-down.

Private Attributes
int	Initial_Heap_Alloc_Size
	Variables that control the memory allocation for the heap.
int	allocatedSize
int	heapCount
	Keeps track of the number of elements in heap.

Detailed Description

Class implementing a heap, which is an auxiliary data structure used for efficient sorting and exploited e.g. by fast marching methods. The main purpose is to sort large lists of real numbers efficiently, at N*log(N) algorithmic complexity.

Definition at line 12 of file heap.h.

Constructor & Destructor Documentation

Heap()

oofem::Heap::Heap

(

int

N

)

Constructor and destructor.

Definition at line 9 of file heap.C.

References allocatedSize, H2T, heapCount, Initial_Heap_Alloc_Size, Keys, N, and T2H.

~Heap()

oofem::Heap::~Heap

(

)

Definition at line 30 of file heap.C.

References H2T, Keys, and T2H.

Member Function Documentation

checkHeapProperty()

int oofem::Heap::checkHeapProperty

(

int

pInd

)

Debugging tools.

Definition at line 196 of file heap.C.

References checkHeapProperty(), heapCount, Keys, lastParentInd(), and leftChildInd().

Referenced by checkHeapProperty().

downHeap()

void oofem::Heap::downHeap ( int Ind )

private

Definition at line 102 of file heap.C.

References heapCount, Keys, and swapElements().

Referenced by getSmallest().

formMatrix()

double * oofem::Heap::formMatrix	(	int	m,
		int	n )

Definition at line 269 of file heap.C.

References H2T, heapCount, and Keys.

getSmallest()

double oofem::Heap::getSmallest

(

int *

Ind

)

Definition at line 176 of file heap.C.

References downHeap(), H2T, heapCount, Keys, and swapElements().

insert()

void oofem::Heap::insert	(	double	time,
		int	Ind )

Definition at line 146 of file heap.C.

References allocatedSize, H2T, heapCount, Initial_Heap_Alloc_Size, Keys, T2H, and upHeap().

isInHeap()

bool oofem::Heap::isInHeap

(

int

Ind

)

Definition at line 136 of file heap.C.

References T2H.

lastParentInd()

int oofem::Heap::lastParentInd ( )

private

Definition at line 56 of file heap.C.

References heapCount.

Referenced by checkHeapProperty().

leftChildInd()

int oofem::Heap::leftChildInd ( int inInd )

private

Definition at line 48 of file heap.C.

Referenced by checkHeapProperty().

nElems()

int oofem::Heap::nElems

(

)

Definition at line 142 of file heap.C.

References heapCount.

parentInd()

int oofem::Heap::parentInd ( int inInd )

private

Index calculations.

Definition at line 44 of file heap.C.

print()

void oofem::Heap::print

(

)

Definition at line 217 of file heap.C.

References heapCount, and Keys.

printTree()

void oofem::Heap::printTree

(

)

Definition at line 250 of file heap.C.

References heapCount, recurse(), and S.

recurse()

void oofem::Heap::recurse ( int row, int pad, int spacing, int S )

private

Used by printTree. Does the actual printing, top-down.

Definition at line 224 of file heap.C.

References heapCount, Keys, MIN, recurse(), and S.

Referenced by printTree(), and recurse().

rightChildInd()

int oofem::Heap::rightChildInd ( int inInd )

private

Definition at line 52 of file heap.C.

setToEmpty()

void oofem::Heap::setToEmpty

(

int

N

)

Interface with external algorithms (such as fast marching).

Definition at line 37 of file heap.C.

References heapCount, N, and T2H.

swapElements()

void oofem::Heap::swapElements ( int Ind1, int Ind2 )

private

Definition at line 63 of file heap.C.

References H2T, Keys, and T2H.

Referenced by downHeap(), getSmallest(), and upHeap().

update()

void oofem::Heap::update	(	double	time,
		int	Ind )

Definition at line 167 of file heap.C.

References Keys, T2H, and upHeap().

upHeap()

void oofem::Heap::upHeap ( int Ind )

private

Elementary heap operations.

Definition at line 87 of file heap.C.

References Keys, and swapElements().

Referenced by insert(), and update().

Member Data Documentation

allocatedSize

int oofem::Heap::allocatedSize

private

Definition at line 43 of file heap.h.

Referenced by Heap(), and insert().

H2T

int* oofem::Heap::H2T

Definition at line 24 of file heap.h.

Referenced by formMatrix(), getSmallest(), Heap(), insert(), swapElements(), and ~Heap().

heapCount

int oofem::Heap::heapCount

private

Keeps track of the number of elements in heap.

Definition at line 46 of file heap.h.

Referenced by checkHeapProperty(), downHeap(), formMatrix(), getSmallest(), Heap(), insert(), lastParentInd(), nElems(), print(), printTree(), recurse(), and setToEmpty().

Initial_Heap_Alloc_Size

int oofem::Heap::Initial_Heap_Alloc_Size

private

Variables that control the memory allocation for the heap.

Definition at line 43 of file heap.h.

Referenced by Heap(), and insert().

Keys

double* oofem::Heap::Keys

Heap arrays: Keys contains certain real values that need to be sorted. The heap is organized according to these, using heap-sort mechanisms. H2T and T2H contain pointers to and from H and T.

Definition at line 23 of file heap.h.

Referenced by checkHeapProperty(), downHeap(), formMatrix(), getSmallest(), Heap(), insert(), print(), recurse(), swapElements(), update(), upHeap(), and ~Heap().

T2H

int* oofem::Heap::T2H

Definition at line 25 of file heap.h.

Referenced by Heap(), insert(), isInHeap(), setToEmpty(), swapElements(), update(), and ~Heap().

---

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

• heap.h
• heap.C