Im trying to make a min-heap as a priority-queue, but there is something about it that make some objects change data when I insert them.
in this example the 17:th object i insert makes the heap crash...
so I wonder if anyone se my mistake and can help me?
this is my "minheap.h"
#ifndef MIN_HEAP_H
#define MIN_HEAP_H
#include <iostream>
using namespace std;
#include "HeapNode.h"
template<class T>
class MinHeap
{
private:
int nrOfElements;
int size;
HeapNode<T> *heap[0];//0 is root
public:
void printHeap()
{
cout << endl << "printHeap" << endl;
int lvl = 0;
cout << nrOfElements << endl;
for(int i=0;i<nrOfElements;i++)
{
cout << *heap->data;
if(i >= lvl)
{
lvl = (lvl*2)+2;
cout << endl;
}
else
{
cout << ",";
}
}
cout << endl << "printHeap DONE" << endl << endl;
}
MinHeap(int theSize)
{
size = theSize;
heap[size];
nrOfElements = 0;
}
void setSize(int nr)
{
nrOfElements = nr;
}
~MinHeap()
{
//delete all
while(!isEmpty())
{
deleteRoot();
reheap_down(0);
}
}
T deleteAt(int i)
{
nrOfElements--;
T temp = heap[nrOfElements]->data;
swap(i,nrOfElements);
reheap_down(i);
return temp;
}
T extract()
{
T item = heap[0]->data;
deleteRoot();
reheap_down(0);
return item;
}
bool insert(T data, int key)
{
if (nrOfElements == size)
{ return false; }
heap[nrOfElements] = new HeapNode<T>(data, key);
reheap_up(nrOfElements);
nrOfElements++;
return true;
}
bool isEmpty()
{
return nrOfElements == 0;
}
T peek()
{
return heap[0]->data;
}
int getSize()
{
return nrOfElements;
}
int isMember(T data)
{
for(int i=0;i<nrOfElements-1;i++)
{
if( *heap->data == *data)
{
return i;
}
}
return -1;
}
T getMember(int i)
{
return *heap->data;
}
private:
void swap(int newNode, int parent)
{
HeapNode<T> *temp = heap[newNode];
heap[newNode] = heap[parent];
heap[parent] = temp;
}
void reheap_up(int newNode)
{
if (newNode > 0)
{
int parent = (int)(newNode-1)/2;
if (heap[newNode]->key < heap[parent]->key)
{
swap(newNode, parent);
reheap_up(parent);
}
}
}
void reheap_down(int parent)
{
int leftChildIndex = 2*parent + 1;
int rightChildIndex = leftChildIndex + 1;
int leftKey = 0;
int rightKey = 0;
if (leftChildIndex <= nrOfElements)
{// At least one child
leftKey = heap[leftChildIndex]->key;
}
if (rightChildIndex <= nrOfElements) // Right child exists
{
rightKey = heap[rightChildIndex]->key;
}
else
{
rightKey = leftKey + 1; // No right child – make sure leftKey smallest
}
int smallChildKey = 0;
int smallChildIndex = 0;
if (leftKey < rightKey)
{
smallChildKey = leftKey;
smallChildIndex = leftChildIndex;
}
else
{
smallChildKey = rightKey;
smallChildIndex = rightChildIndex;
}
// Need to swap parent with largest child?
if (heap[parent]->key > smallChildKey && leftChildIndex <= nrOfElements)
{
swap(parent, smallChildIndex);
reheap_down(smallChildIndex);
}
}
void deleteRoot()
{
if(isEmpty())
{ return; }
nrOfElements--;
swap(0,nrOfElements);
}
};
#endif
this is my "intNode.h" that I use to test the heap
#ifndef INTNODE_H
#define INTNODE_H
#include <iostream>
using namespace std;
class intNode
{
public:
int number;
intNode(int i)
{
number = i;
}
friend ostream &operator<<(ostream &o, const intNode &node)
{
o << node.number;
return o;
}
bool operator==(intNode& node)
{
return number == node.number;
}
};
#endif
And this is my main.cpp to test it all
#include <iostream>
using namespace std;
#include "MinHeap.h"
#include "intNode.h"
MinHeap<intNode*> *pq;
int main()
{
pq = new MinHeap<intNode*>(3600);
pq->insert(new intNode(1),1);
pq->insert(new intNode(2),2);
pq->insert(new intNode(3),3);
pq->insert(new intNode(4),4);
pq->insert(new intNode(5),5);
pq->insert(new intNode(6),6);
pq->insert(new intNode(7),7);
pq->insert(new intNode(8),8);
pq->insert(new intNode(9),9);
pq->insert(new intNode(10),10);
pq->insert(new intNode(11),11);
pq->insert(new intNode(12),12);
pq->insert(new intNode(13),13);
pq->insert(new intNode(14),14);
pq->insert(new intNode(15),15);
pq->insert(new intNode(16),16);
pq->printHeap();
pq->insert(new intNode(17),17);
pq->insert(new intNode(18),18);
pq->printHeap();
system("pause");
return 0;
}
