File : BHeap.h
/*
This is a class implementation of Binary Heap to optimize A*
It has O(log n) for insertion and deletion to the heap with sorting capability
*/
#ifndef BHEAP_H
#define BHEAP_H
#include <iostream>
#include <string>
using namespace std;
template<class T>
class BHeap
{
public:
BHeap() : DEFAULT_SIZE(100){
data = new T[DEFAULT_SIZE];
m_capacity = DEFAULT_SIZE;
m_count = 0;
}
~BHeap(){
delete [] data;
}
int size() const{
return m_count;
}
bool isEmpty() const{
return m_count == 0;
}
void setCapacity(int newCapacity){
if ( newCapacity > m_capacity){
//allocate new capacity
T *newData = new T[newCapacity];
memcpy_s(newData, newCapacity, data, m_count);
m_capacity = newCapacity;
//copy old data to new data
data = newData;
delete [] newData;
}
}
void Add(T item);
void DownHeap();
void UpHeap();
T Peek();
T Remove();
private:
const int DEFAULT_SIZE;
T *data; //array of data in the heap
int m_count; //count the number of element in the heap
int m_capacity; //to indicate the current capacity in the heap
bool sorted; //boolean variable to test whether it is sorted
int Child1(int idx){
return (idx << 1) + 1; //Child 1 index = (2 * parentIndex) + 1
}
int Child2(int idx){
return (idx << 1) + 2; //Child 2 index = (2 * parentIndex ) +2
}
int Parent(int idx){
return (idx - 1 ) >> 1; //Parent index = (childIndex -1 ) / 2
}
//void EnsureSort();
};
//#include "BHeap.cpp"
#endif
File: BHeap.cpp
#include "BHeap.h"
//template<typename T>
//BHeap<T>::BHeap() : DEFAULT_SIZE(100)
//{
// data = new T[DEFAULT_SIZE];
// m_capacity = DEFAULT_SIZE;
// m_count = 0;
//}
//
//template<typename T>
//BHeap<T>::~BHeap()
//{
// delete [] T;
//}
template<class T>
T BHeap<T>::Peek(){
return data[0];
}
template<class T>
void BHeap<T>::Add(T item){
if ( m_count == m_capacity){
setCapacity(2 * m_capacity);
}
data[m_count] = item;
UpHeap();
m_count++;
}
template<class T>
void BHeap<T>::DownHeap(){
///TODO:
int currentIdx =0;
int n;
T item = data[currentIdx]; //we try to bubble down the root element
while(true){
int child1, child2;
child1 = Child1(currentIndex);
child2 = Child2(currentIndex);
//find the correct comparison index of child1 and child2
if ( child1 >= m_count)
break;
if ( child2 >= m_count)
n = child1;
else{
n = (data[child1] < data[child2] )? child1 : child2;
}
//swap nodes if necessary
if ( item > data[n]){ //if item is greater than data[n]
data[currentIndex] = data[n];
currentIndex = n;
}
else{
break;
}
}
data[n] = item;
}
template<class T>
void BHeap<T>::UpHeap(){
///TODO:
int childIndex = m_count;
T item = data[childIndex];
int parentIndex = Parent(childIndex);
while (parentIndex > -1 && item < data[parentIndex])
{
data[childIndex] = data[parentIndex]; //Swap nodes
childIndex = parentIndex;
parentIndex = Parent(childIndex);
}
data[childIndex] = item;
}
template<class T>
T BHeap<T>::Remove(){
if ( isEmpty()){
cout << "Heap is already empty " << endl;
return NULL;
}
T v = Peek();
m_count--;
data[0] = data[m_count];
data[m_count] = default(T);
DownHeap();
return v;
}
Problem: I cannot use the BHeap implementation:
#include <cstdlib>
#include <time.h>
using namespace std;
#include "BHeap.h"
int main(int argc, char *argv[]){
BHeap< int > heapInt;
srand(time(NULL));
//Add random elements
for(int i = 0 ; i < 10; i++){
int el = 1 + rand() %100;
heapInt.Add( el);
cout << "Element (inserted): "<< el << endl;
}
//Remove all elements
while( heapInt.size() > 0){
int el = heapInt.Remove();
cout << "Element (removed): " << el << endl;
}
return 0;
}
