Jump to content

  • Log In with Google      Sign In   
  • Create Account


Min Heap Using C++ Template


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 Nemean Charisma   Members   -  Reputation: 122

Like
0Likes
Like

Posted 05 March 2012 - 07:35 AM

Hi I have tried to implement Binary Heap(Min priority queue) using C++ Templates. But when I test it inside my main program, it cannot compile. Do you have any idea?

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;
}


Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9565

Like
0Likes
Like

Posted 05 March 2012 - 07:41 AM

When you have a compiler error, you should, at a minimum, post what the compiler error actually is.

#3 Brother Bob   Moderators   -  Reputation: 8040

Like
1Likes
Like

Posted 05 March 2012 - 07:41 AM

The short story is; you cannot put the definition of a template in a separate translation unit. Read more here.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS