Jump to content
  • Advertisement
Sign in to follow this  
Woblin

my first min-heap in c++

This topic is 4438 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
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!