• Advertisement
Sign in to follow this  

my first min-heap in c++

This topic is 4346 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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


Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement