Heap Class Reference

A simple & efficient Heap class which uses Graph objects. More...

#include <Heap.h>

Public Member Functions
	Heap (int s=DEFAULT_SIZE)
	~Heap ()
unsigned int	size ()
void	Add (graph_object *val)
	Add object into Heap. More...
void	DecreaseKey (graph_object *val)
	Indicate that the key for a particular object has decreased. More...
bool	IsIn (graph_object *val)
	Returns true if the object is in the Heap. More...
graph_object *	Remove ()
	Remove the item with the lowest key from the Heap & re-heapify. More...
bool	Empty ()
	Returns true if no items are in the Heap. More...

Private Member Functions
void	HeapifyUp (int index)
void	HeapifyDown (int index)

Private Attributes
std::vector< graph_object * >	_elts
int	count

Detailed Description

A simple & efficient Heap class which uses Graph objects.

Definition at line 27 of file Heap.h.

Constructor & Destructor Documentation

Heap()

Heap::Heap

(

int

s = DEFAULT_SIZE

)

Definition at line 18 of file Heap.cpp.

References _elts, and count.

~Heap()

Heap::~Heap

(

)

Definition at line 24 of file Heap.cpp.

Member Function Documentation

Add()

void Heap::Add

(

graph_object *

val

)

Add object into Heap.

Definition at line 36 of file Heap.cpp.

References _elts, count, HeapifyUp(), and graph_object::key.

Referenced by praStar::astar(), GraphMapInconsistentHeuristic::FillInCache(), GraphDistanceHeuristic::FindFarNode(), corridorAStar::getBestPath(), GraphDistanceHeuristic::GetOptimalDistances(), and aStarOld::GetPath().

DecreaseKey()

void Heap::DecreaseKey

(

graph_object *

val

)

Indicate that the key for a particular object has decreased.

Definition at line 47 of file Heap.cpp.

References HeapifyUp(), and graph_object::key.

Referenced by GraphMapInconsistentHeuristic::FillInCache(), GraphDistanceHeuristic::FindFarNode(), GraphDistanceHeuristic::GetOptimalDistances(), aStarOld::relaxEdge(), corridorAStar::relaxEdge(), praStar::relaxEdge(), corridorAStar::relaxFinalEdge(), and corridorAStar::relaxFirstEdge().

Empty()

bool Heap::Empty

(

)

Returns true if no items are in the Heap.

Definition at line 83 of file Heap.cpp.

References count.

Referenced by GraphMapInconsistentHeuristic::FillInCache(), GraphDistanceHeuristic::FindFarNode(), GraphDistanceHeuristic::GetOptimalDistances(), and Remove().

HeapifyDown()

void Heap::HeapifyDown ( int  index )

private

Definition at line 104 of file Heap.cpp.

References _elts, count, and fless().

Referenced by Remove().

HeapifyUp()

void Heap::HeapifyUp ( int  index )

private

Definition at line 88 of file Heap.cpp.

References _elts, and fgreater().

Referenced by Add(), and DecreaseKey().

IsIn()

bool Heap::IsIn

(

graph_object *

val

)

Returns true if the object is in the Heap.

Definition at line 55 of file Heap.cpp.

References _elts, and graph_object::key.

Referenced by praStar::astar(), GraphMapInconsistentHeuristic::FillInCache(), GraphDistanceHeuristic::FindFarNode(), corridorAStar::getBestPath(), GraphDistanceHeuristic::GetOptimalDistances(), and aStarOld::GetPath().

Remove()

graph_object * Heap::Remove

(

)

Remove the item with the lowest key from the Heap & re-heapify.

Definition at line 66 of file Heap.cpp.

References _elts, count, Empty(), and HeapifyDown().

Referenced by praStar::astar(), GraphMapInconsistentHeuristic::FillInCache(), GraphDistanceHeuristic::FindFarNode(), corridorAStar::getBestPath(), GraphDistanceHeuristic::GetOptimalDistances(), and aStarOld::GetPath().

size()

unsigned int Heap::size

(

)

Definition at line 28 of file Heap.cpp.

References _elts.

Member Data Documentation

_elts

std::vector<graph_object *> Heap::_elts

private

Definition at line 40 of file Heap.h.

Referenced by Add(), Heap(), HeapifyDown(), HeapifyUp(), IsIn(), Remove(), and size().

count

int Heap::count

private

Definition at line 41 of file Heap.h.

Referenced by Add(), Empty(), Heap(), HeapifyDown(), and Remove().

---

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

• /home/sturtevant/nightly/hog2/graphalgorithms/Heap.h
• /home/sturtevant/nightly/hog2/graphalgorithms/Heap.cpp