asked on

need help w/ HEAP piece of code

Below is parts of my implemetation file. Below the code is my question:

/*********************************************************************/
/* removeMin */
/*************/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::removeMin()
{
if( isEmpty() )
{
cout << "The heap is empty!" << endl;
exit (-1 );
}

array[1] = array[heapSize--];
//percolateDn(1);

int left = 0;
int right = 0;
int curent_pos = 0;
int rtChild = 2 * (curent_pos + 1);
int ltChild = (2 * curent_pos) + 1;

while(!isLeaf(curent_pos))
{ cout << "here" <<endl; //test to see if makes into here
/* get copy of both children */
left = leftChild(curent_pos);
cout << left << endl; //check to see number
right = rightChild(curent_pos);
cout << right << endl; //check to see number
/* swap with the smaller of the two */
if (left < right)
{
swap( ltChild, curent_pos);
/* set the new position */
curent_pos = ltChild;
}
else
{
swap( rtChild, curent_pos);
/* set the new position */
curent_pos = rtChild;
}
}
}

/*********************************************************************/
/* rightChild */
/**************/

template <class NodeInfo>
int MinBinHeap<NodeInfo>::rightChild( int current_pos )
{

return array[ 2 * (current_pos + 1) ];
}

/*********************************************************************/

/*********************************************************************/
/* leftChild */
/*************/

template <class NodeInfo>
int MinBinHeap<NodeInfo>::leftChild( int current_pos )
{

return array[ (2*current_pos) + 1 ];
}

template <class NodeInfo>
bool MinBinHeap<NodeInfo>::isLeaf( int check )
{
//cout << "here2 " << heapSize <<endl;
// If true, not a leaf
return( check < (heapSize/2) && (check < heapSize) );
}

/*********************************************************************/

/*********************************************************************/
/* swap */
/********/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::swap( int child, int current_pos )
{
int temp;

temp = current_pos;
array[temp] = array[child];
array[child] = array[temp];
}

/*********************************************************************/

It is removing the first element int the heap and replacing it with the last element in the heap. Then it is checking for isLeaf. From here it should check to see if it is a leaf then go into the while loop. It is not getting into the while. If I change the code to make it go into the while loop, it goes into an infinite loop for some reason. Apparantly I am not catching something here.

PLEASE HELP!! I would be greatful.

THANKS!!

novitiate

if you can post full code, that would help in answering your question fast.

_novi_

jhshukla

hey novi, care to participate in / look at this question? f15e is having problems only with deletion (as stated there).
https://www.experts-exchange.com/questions/21333488/delete-min-item-in-Heap-trouble.html

f15e, since your problem is not solved yet, you can go to the CS TA and ask a moderator to reopen old question. it's completely up to you. if you want further discussion in this thread, say so and I will post here from now on.

novitiate

thats authentic jhshukla, appreciate that.

_novi_

f15e

ASKER

I am still have some difficultly w/ my removeMin() function. I need some serious help. I am not an expert coder by any means and I haven't coded in over a year so I am very rusty. Anyway, the only part of my code that doesn't work, as far as I know, is the removeMin() function. I have listed my code below. Is it possible to attach some documents here instead of putting the whole code in this box? Below is my driver.cpp (1st), then my implementation.cpp (2nd), and finally my heap.h file with the appropriate file name before the code begins: (I have commented out parts of the code where I was testing to see the output at that point for debugging. The problem lies within the removeMin() function or one of the other functions that is called from removeMin().) Thanks for your help.

/****************************************************************/
/* driver.cpp */

#include <iostream>
#include "heap.h"

using namespace std;

int main()
{
      MinBinHeap<int> heap( 100 );

      int num;

      cout << "Enter 8 numbers into the heap:" <<endl;
      for(int i = 0; i < 8; i++)
            {
                  cout << i+1 << ". ";
                  cin >> num;
                  heap.insert(num);
            }

      heap.viewHeap();
      cout << endl << "Enter a number to put into the Heap: ";
      cin >> num;
      heap.insert(num);
      heap.viewHeap();
      cout << endl << "Enter a number to put into the Heap: ";
      cin >> num;
      heap.insert(num);
      heap.viewHeap();

      cout << endl << "The smallest value in the heap is "
       << heap.findMin() << endl <<endl;
      heap.removeMin();
      heap.viewHeap();


      return 0;
}

/*************************************************************************/

/* implementation.cpp */

#include <iostream>
#include "MinBinHeap.h"

/*********************************************************************/
/* CONSTRUCTOR */
/***************/

template <class NodeInfo>
MinBinHeap<NodeInfo>::MinBinHeap(int MAX_SIZE)
{
      heapSize = 0;
      allocatedSize = MAX_SIZE;
      array = new NodeInfo[MAX_SIZE];
}

/*********************************************************************/

/*********************************************************************/
/* DESTRUCTOR */
/**************/

template <class NodeInfo>
MinBinHeap<NodeInfo>::~MinBinHeap()
{
      delete[] array;
}

/*********************************************************************/

/*********************************************************************/
/* buildHeap */
/*************/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::buildHeap( ) //( NodeInfo myArray[], int x)
{
      /*
      for( int i = 0; i < x; i++ )
            //array[i+1] = myArray[i]; */



      for( int i = heapSize/2; i > 0; i-- )
            percolateDn(i);
}

/*********************************************************************/

/*********************************************************************/
/* insert */
/**********/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::insert( const NodeInfo& x )
{
      if( isFull() )
      {
            cout << "The heap is full!" << endl;
            exit (-1 );
      }

       // Percolate Up
      int hole = ++heapSize;
      for( ; hole > 1 && x < array[hole/2]; hole /= 2)
            array[hole] = array[hole/2];
      array[hole] = x;

      //heapSize++;

      //currentPos = heapSize;




      /*
      while( currentPos > 1 && x < array[currentPos/2]);
      {
            array[currentPos] = array[currentPos/2];
            currentPos /= 2;
      }*/

      //array[heapSize];
}

/*********************************************************************/

/*********************************************************************/
/* removeMin */
/*************/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::removeMin()
{
      if( isEmpty() )
      {
            cout << "The heap is empty!" << endl;
            exit (-1 );
      }

      array[1] = array[ heapSize-- ];




      //cout << " heap = " << heapSize <<endl;
      //int num = array[heapSize];
      //cout << num <<endl;

      //array[0] = num;
      //cout << " heap = " << heapSize <<endl;
      viewHeap();
      //cout << "array 0 = " << array[0] <<endl;


      //percolateDn(1);


      int left;
      int right;
      int current_pos = 0;
      NodeInfo tempArray[2];


      while( not(isLeaf(current_pos)) )
      {
             //get copy of both children

            left = leftChild(current_pos);
            //tempArray[0] = array[left];
            //cout << tempArray[0] << " temp left here." <<endl;
      //      cout << "left is " <<left << endl;



            right = rightChild(current_pos);
            //tempArray[1] = array[right];
            //cout << tempArray[1] << " temp right here." <<endl;

            //cout << "right is " << right << endl; //check to see number
            /* swap with the smaller of the two */

            //cin.get();
            //cout << "left before get into if " << left <<endl;
      //      cout << "RIGHT before get into if " << right <<endl;
            //cout << array[left+1] << " " << array[right+1] << endl;

            if (array[left+1] < array[right+1])
            {
            //left = tempArray[0];

            swap( left, current_pos);
            /* set the new position */
            //cout << "left after gets back from swap" << left<<endl;
             current_pos = left;
            }
            else
            {
            //right = tempArray[1];
            swap( right, current_pos);
            /* set the new position */
            current_pos = right;
            }

      }
}

/*********************************************************************/

/*********************************************************************/
/* removeMin */
/*************/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::removeMin( NodeInfo & minItem )
{
      if( isEmpty() )
      {
            cout << "The heap is empty!" << endl;
            exit (-1 );
      }

      minItem = array[1];
      array[1] = array[heapSize--];
      percolateDn(1);

}

/*********************************************************************/

/*********************************************************************/
/* findMin */
/***********/

template <class NodeInfo>
const NodeInfo & MinBinHeap<NodeInfo>::findMin() const
{
      if( isEmpty() )
      {
            cout << "The heap is empty!" << endl;
            exit( -1 );
      }

      return array[1];
}

/*********************************************************************/

/*********************************************************************/
/* isEmpty */
/***********/

template <class NodeInfo>
bool MinBinHeap<NodeInfo>::isEmpty () const
{
      return heapSize == 0;
}

/*********************************************************************/

/*********************************************************************/
/* isFull */
/***********/

template <class NodeInfo>
bool MinBinHeap<NodeInfo>::isFull () const
{
      return heapSize == allocatedSize - 1;
}

/*********************************************************************/

/*********************************************************************/
/* percolateDn */
/***************/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::percolateDn( int currentPos )
{
      int child;

      NodeInfo temp = array[currentPos];

      for( ; 2*currentPos <= heapSize; currentPos = child )
      {
            child = 2*currentPos;

            if( child != heapSize && array[child+1] < array[child] )
                  child++;

            if( array[child] < temp )
                  array[currentPos] = array[child];
            else
                  break;

            array[currentPos] = temp;
      }

      array[currentPos] = temp;
}

/*********************************************************************/

/*********************************************************************/
/* viewHeap */
/************/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::viewHeap()
{ //testing - take below out
      //cout << "Heap size is " << heapSize << endl<<endl;

      if( isEmpty() )
            cout << "The heap is empty!" << endl;


      else
      {
            for( int i = 1; i <= heapSize; i++ )
                  cout << array[i] << ' ';

            cout << endl;
      }


}

/*********************************************************************/

/*********************************************************************/
/* rightChild */
/**************/

template <class NodeInfo>
int MinBinHeap<NodeInfo>::rightChild( int current_pos )
{
      //int currentPos = 0;

      /*for( int i = 1; i < heapSize; i++ )
      {
            if( array[i] = input )
            {
                  currentPos = i;
                  break;
            }
      }*/

      cout << current_pos << endl;
      cout << "Right child in its function is " << array[ 2 * (current_pos + 1)+ 1] << endl;
      return 2 * (current_pos + 1) ;
}

/*********************************************************************/

/*********************************************************************/
/* leftChild */
/*************/

template <class NodeInfo>
int MinBinHeap<NodeInfo>::leftChild( int current_pos )
{
      /*

      for( int i = 1; i < heapSize; i++ )
      {
            if( array[i] = current_pos )
            {
                  currentPos = i;
                  break;
            }
      }*/
//}: Command not found

      cout << current_pos << endl;
      cout << "Left child in its function is " <<array[ (2*current_pos + 1) + 1 ] << endl;

      return (2*current_pos) + 1;
}

/*********************************************************************/

/*********************************************************************/
/* parent */
/**********/

template <class NodeInfo>
int MinBinHeap<NodeInfo>::parent( int input )
{
      int currentPos = 0;

      for( int i = 1; i < heapSize; i++ )
      {
            if( array[i] = input )
            {
                  currentPos = i;
                  break;
            }
      }


      return currentPos - 1/2;
}

/*********************************************************************/

/*********************************************************************/

template <class NodeInfo>
bool MinBinHeap<NodeInfo>::isLeaf( int check )
{
//      cout << "isleaf check " << check << endl;
      return not(check < heapSize/2);
}

/*********************************************************************/

/*********************************************************************/
/* swap */
/********/

template <class NodeInfo>
void MinBinHeap<NodeInfo>::swap( int child, int current_pos )
{
//      cout << "swap in child is " << child << " and curr pos is " << current_pos <<endl;
      int tempArray[1];


      tempArray[1]=array[current_pos];


      array[current_pos] = array[child];
      array[child] = tempArray[1];

}

/*********************************************************************/

/* heap.h */

#ifndef MIN_BIN_HEAP_H
#define MIN_BIN_HEAP_H

template <class NodeInfo>
class MinBinHeap
{
      public:
            MinBinHeap ( int MAX_SIZE = 100 );

            bool isEmpty () const;
            bool isFull () const;

            void insert ( const NodeInfo& );
            const NodeInfo & findMin () const;
            void removeMin ();
            void removeMin ( NodeInfo & minItem );
            void viewHeap ();
            ~MinBinHeap ();

      private:
            NodeInfo *array;

            int heapSize; // # elements in heap
            int allocatedSize; // # elements in array

            void buildHeap (); // ( NodeInfo*, int );
            void percolateDn ( int );
            void swap ( int, int );

            int parent ( int );
            int leftChild ( int );
            int rightChild ( int );
            bool isLeaf ( int );

};

#endif
/************************************************************/

jhshukla

template <NodeInfo>
void MinHeap<NodeInfo>::swap(int one, int two){
NodeInfo tmp = array[one];
array[one] = array[two];
array[two] = tmp;
return;
}

=====================================
/* removeMin */

template <class NodeInfo>
void MinBinHeap<NodeInfo>::removeMin( NodeInfo & minItem )
{
if( isEmpty() )
{
cout << "The heap is empty!" << endl;
exit (-1 );
}

// all these should use 0 instead of 1
minItem = array[1];
array[1] = array[heapSize--];
percolateDn(1);

}

=================================
/* percolateDn */

template <class NodeInfo>
void MinBinHeap<NodeInfo>::percolateDn( int currentPos )
{
int child;

NodeInfo temp = array[currentPos];

for( ; 2*currentPos <= heapSize; currentPos = child ) // better use '2*currentPos < heapSize' or the prog might crash
{
child = 2*currentPos; // aren't you missing something here? may be +1.

if( child != heapSize && array[child+1] < array[child] )
child++;

if( array[child] < temp ) // this will always be true because current holds the MAX value in the heap
array[currentPos] = array[child];
else
break;

array[currentPos] = temp; // you forgot to update currentPos
}

array[currentPos] = temp;
}

ASKER CERTIFIED SOLUTION

jhshukla

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

f15e

ASKER

OK, as you can see I am not a great coder. Pretty much a beginner. Anyway, from the above removeMin(NodeInfo & minItem), I am calling removeMin from my driver that before had no parameters but now with this code, it has a parameter. What exactly do I put in as the param in the driver when I call removeMin. Thanks for your help!!

f15e

ASKER

Thank you very much jhshukla! That helped out significantly. With about 10 minutes to spare, I got the code to work perfectly. Thanks again!

jhshukla

you are welcome.
>> /* percolateDn */
>> if( array[child] < temp ) // this will always be true because current holds the MAX value in the heap
that's another mistake that I made. yes, you need the comparision.

and you don't need to pass any parameters to removeMin(). it is supposed to remove the minimum value from the heap. If you had something else like removeItem(int index), then you would pass the index of the item that you want to remove and call percolateDn(index) from there.
I don't know what the parameter that is passed to removeMin is for. I think that there should be a different function called remove() instead of removeMin(). Could tell me what you are supposed to do with the new item that you get? that way we can come up with some sort of algorithm or something.

jaydutt