BinaryHeap Class Reference

A BinaryHeap is to be used as a priority queue. More...

#include <BinaryHeap.h>

List of all members.

Public Member Functions

 BinaryHeap (int)
 allocate heap of n elements
 ~BinaryHeap ()
 Destructor frees all internal storage.
bool isEmpty ()
int smallest ()
 Return the vertex identifier of the smallest vertex in heap and readjust the heap.
void insert (int, int)
 Insert the given value into the tree with priority.
void decreaseKey (int, int)
 Find the vertex with identifier [id] and reduce its priority to the given value.

Private Attributes

int _n
ELEMENT_PTR _elements
int * _pos
long _numComparisons
long _numInsert
long _numSwaps
long _numSmallest
long _numDecrease


Detailed Description

A BinaryHeap is to be used as a priority queue.


Constructor & Destructor Documentation

BinaryHeap::BinaryHeap ( int   ) 

allocate heap of n elements

BinaryHeap::~BinaryHeap (  ) 

Destructor frees all internal storage.


Member Function Documentation

void BinaryHeap::decreaseKey ( int  id,
int  newPriority 
)

Find the vertex with identifier [id] and reduce its priority to the given value.

It is the responsibility of the caller to ensure that this function is only invoked when newPriority is indeed smaller than the existing priority associated with the id.

Parameters:
id information to have priority reduced.
newPriority priority which must be smaller than existing priority.

void BinaryHeap::insert ( int  id,
int  priority 
)

Insert the given value into the tree with priority.

Ties are broken in favor of insert.

Parameters:
id id of information to be stored
priority priority to associate with this id.

bool BinaryHeap::isEmpty (  )  [inline]

int BinaryHeap::smallest (  ) 

Return the vertex identifier of the smallest vertex in heap and readjust the heap.


Member Data Documentation

ELEMENT_PTR BinaryHeap::_elements [private]

int BinaryHeap::_n [private]

long BinaryHeap::_numComparisons [private]

long BinaryHeap::_numDecrease [private]

long BinaryHeap::_numInsert [private]

long BinaryHeap::_numSmallest [private]

long BinaryHeap::_numSwaps [private]

int* BinaryHeap::_pos [private]


The documentation for this class was generated from the following files: Algorithm Development Kit 1.0