oofem::Heap Class Reference

Class implementing a heap, which is an auxiliary data structure used for efficient sorting and exploited e.g. More...

#include <heap.h>

Public Member Functions
	Heap (int N)
	Constructor and destructor. More...
	~Heap ()
void	setToEmpty (int N)
	Interface with external algorithms (such as fast marching) More...
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. More...
void	print ()
void	printTree ()
double *	formMatrix (int m, int n)

Public Attributes
double *	Keys
	Heap arrays: Keys contains certain real values that need to be sorted. More...
int *	H2T
int *	T2H

Private Member Functions
void	upHeap (int Ind)
	Elementary heap operations. More...
void	downHeap (int Ind)
void	swapElements (int Ind1, int Ind2)
int	parentInd (int inInd)
	Index calculations. More...
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. More...

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

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

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.

oofem::Heap::~Heap

(

)

Definition at line 30 of file heap.C.

References H2T, Keys, and T2H.

Member Function Documentation

int oofem::Heap::checkHeapProperty

(

int

pInd

)

Debugging tools.

Definition at line 196 of file heap.C.

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

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

private

Definition at line 102 of file heap.C.

References heapCount, Keys, and swapElements().

Referenced by getSmallest().

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

Definition at line 269 of file heap.C.

References H2T, heapCount, and Keys.

double oofem::Heap::getSmallest

(

int *

Ind

)

Definition at line 176 of file heap.C.

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

Referenced by oofem::Grid::fastMarch().

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().

Referenced by oofem::Grid::fastMarch().

bool oofem::Heap::isInHeap

(

int

Ind

)

Definition at line 136 of file heap.C.

References T2H.

Referenced by oofem::Grid::fastMarch().

int oofem::Heap::lastParentInd ( )

private

Definition at line 56 of file heap.C.

References heapCount.

Referenced by checkHeapProperty().

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

private

Definition at line 48 of file heap.C.

Referenced by checkHeapProperty().

int oofem::Heap::nElems

(

)

Definition at line 142 of file heap.C.

References heapCount.

Referenced by oofem::Grid::fastMarch().

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

private

Index calculations.

Definition at line 44 of file heap.C.

void oofem::Heap::print

(

)

Definition at line 217 of file heap.C.

References heapCount, and Keys.

void oofem::Heap::printTree

(

)

Definition at line 250 of file heap.C.

References heapCount, recurse(), and S.

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, and S.

Referenced by printTree().

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

private

Definition at line 52 of file heap.C.

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.

Referenced by oofem::Grid::unFreeze().

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().

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

Definition at line 167 of file heap.C.

References Keys, T2H, and upHeap().

Referenced by oofem::Grid::fastMarch().

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

int oofem::Heap::allocatedSize

private

Definition at line 43 of file heap.h.

Referenced by Heap(), and insert().

int* oofem::Heap::H2T

Definition at line 24 of file heap.h.

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

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().

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().

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().

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