#include <BinaryHeap.h>
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 |
BinaryHeap::BinaryHeap | ( | int | ) |
allocate heap of n elements
BinaryHeap::~BinaryHeap | ( | ) |
Destructor frees all internal storage.
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.
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.
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.
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] |