I'm working on a simple c++ project to implement a Heap class and use it's functions. I have written out most of the code, and when I went to try out some of the functions, the console would tell me that I have unreferenced symbols when I try to compile. Below is the code.
Heap.h:
#ifndef HEAP_H
#define HEAP_H
template<typename T>
class Heap {
T arr[100];
int heapSize;
//int parent(int);//returnts the index of the parent
int leftChild(int);//returns the index of the left child
int rightChild(int);//returns the index of the right child
void heapify(T*,int);//made to build the heap;
void buildHeap();//constructs the heap
public:
Heap();//default constructor
Heap(T[], int);//custom constructer accepts an array of type T and size
~Heap();//destructor
void insert(T);//insert a node into the array
// void heapSort(T*);
T extractMax (); //return root value and remove it from heap
T maximum();//return the maximum
void printHeap();//print the values of the heap
};
#endif
Heap.cpp :
#include "Heap.h"
#include <iostream>
template<typename T>
Heap<T>::Heap() { heapSize = 0; }
template<typename T>
Heap<T>::Heap(T a[], int size) {//accepts an array of Type T
for(int i =0; i < size; i++)
arr[i] = a[i];
heapSize = size;
buildHeap();
}
template<typename T>
Heap<T>::~Heap() { }
template<typename T>
int Heap<T>::leftChild(int i) { return ((i*2) + 1); } //the left child is given by index*2 +1
template<typename T>
int Heap<T>::rightChild(int i) { return ((i*2) + 2); } //the right child is given by index*2 +2
template<typename T>
void Heap<T>::heapify(T* a, int i )
{
int left, right, largest;
T temp;
left = leftChild(i);//get the index for the left child
right = rightChild(i);//get the index for the right child
if((left <= heapSize) && a[left] > a[i])//check which index has the largest value and store it
//also checks if the index is within the heap size
largest = left;
else
largest = i;
if((right <= heapSize) && a[right] > a[largest])//check if right child is larger
largest = right;
if(largest != i)//swap the values of the child is larger than parent
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, largest);
}
}
template<typename T>
void Heap<T>::buildHeap()
{
int hSize = heapSize;//takes the size of the heap
for(int i = ((hSize/2)-1); i >= 0 ; i--)//loops through every node to make sure they are sorted
heapify(arr, i);
}
template<typename T>
T Heap<T>::maximum() { return arr[0]; } //return the first element or root element;
template<typename T>
T Heap<T>::extractMax() //removes the root element and returns it
{
T max = arr[0];
T* temp = new T[heapSize-1];//create a temp array
for(int i = 0; i < heapSize; i++)//store all old vals to temp arr except for first element;
temp[i] = arr[i+1];
arr = temp;//set arr to temp array
heapSize--;//decerease heapsize
buildHeap(); //rebuild heap
return max; //return root value;
}
template<typename T>
void Heap<T>::insert(T add) //add is the new element for the heap
{
arr[heapSize] = add;//add the new element to the end of the arr
heapSize++;//increase heapsize
buildHeap(arr, heapSize);//call buildHeap to rebuild and resort the heap with the new element
}
template<typename T>
void Heap<T>::printHeap()
{
for(int i =0; i < heapSize; i++)
std::cout<<arr[i];
}
Main.cpp:
#include "Heap.h"
#include <iostream>
using namespace std;
int main()
{
int arr[] = {6,7,9,10,2,4,5};
Heap<int> heap(arr, 7);
heap.printHeap();
return 0;
}
My makefile:
all: heapmake
heapmake: Main.o Heap.o
g++ Main.o Heap.o -o heapmake
Main.o:Main.cpp
g++ -c Main.cpp
Heap.o:Heap.cpp
g++ -c Heap.cpp
clean:
rm *o heapmake
I suspect that I am not linking the files together properly but I thought I'd post all the code just in case.
