?
Solved

HELP with removeMIn function c++  URGENT

Posted on 2005-03-02
8
Medium Priority
?
244 Views
Last Modified: 2010-04-01
I posted this earlier within a question I already had but no one responded.  I have given below my complete code. I am still have some difficultly w/ my removeMin() function.  I have about 2 hours to get this part to work.  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.  I would appreciate it if someone could run this code and tell me what part is going wrong in the removeMIn class memeber. THANK YOU VERY MUCH!!!

/****************************************************************/
/*                       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
/************************************************************/
 
0
Comment
Question by:f15e
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
8 Comments
 
LVL 8

Expert Comment

by:novitiate
ID: 13446391
one thing that I can tell you is, your swap function is wrong.

corrected one...

template <typename 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[0]=array[current_pos];
     
     
     array[current_pos] = array[child];
     array[child] = tempArray[0];
     
}

more better would be
template <typename NodeInfo>
void MinBinHeap<NodeInfo>::swap( int child, int current_pos )
{
//     cout << "swap in child is " << child << "  and curr pos is " << current_pos <<endl;
     NodeInfo temp;
     
     
     temp=array[current_pos];
     
     
     array[current_pos] = array[child];
     array[child] = temp;
     
}
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13447409
novi has it right, the swap function is wrong. If you are defining

     int tempArray[1];  

you create an array with 1 element (makes no sense). I suppose you want create one array element, but that isn't an array of ints but only a int:

    int temp = array[current_pos];       // save current
    array[current_pos] = array[child];   // set new current
    array[child] = temp;                       // set new child
   

Some comments to removeMin

>>>>     minItem = array[1];

Here it looks like the same error as with swap. array[1] is the 2. element of array. If your array is sorted the minimum is array[0].

>>>>     array[1] = ...

Same applies here. With array[1] you overwrite the second array element.

What is the purpose of removeMin ? If it should remove the minimum, then you would have to shift all array elements by 1 to the left and decrease the element size. Actually I can't see that code.

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

That is only 1 assignment and both indices are wrong (I think so). [1] we already discussed. If heapSize is the number of elements in the array - actually not a good name -, then array[heapSize] is one element *beyond* the last element, e. g. heapSize = 10  and array[heapSize] is the 11.th element  0, 1, 2, ...., 10.

>>>> heapSize--

decrementing heapsize but *after* the wrong index is used

>>>>     percolateDn(1);  

Actually, I don't know what's the purpose of that call.

If you would like to remove the minimum array value, you would need something like that:

  --heapSize;
  for (int i = 0; i < heapSize; ++i)
        array[i] = array[i+1];

Regards, Alex
0
 

Author Comment

by:f15e
ID: 13451600
Thank you very much guys for responding.  I finally got the code to work as it should.  Thanks again!
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 9

Expert Comment

by:jhshukla
ID: 13453625
f15e, I don't know what to tell you. you opened three threads for the same problem and had different experts working on it. now you accepted the solution posted in one thread and you are saying here that you got it to work. no reference of how and where you got the solution from. opening multiple threads for same question surely catches attention but solution is delayed. people are confused and what not. since you are a very recent member I don't know how moderators will act but if you were to do this after quite a while, almost certainly you would lose points and question would be deleted. no one would benefit from that. If no one responds to your question, you can post a 'pointer' question, briefly stating the problem and providing a link to the original question.

for all the other experts who have participated here:
http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_21334130.html

and novi, you knew about this. didn't you?

Alex, this code is wrong. it is a minHeap not a sorted array.
  --heapSize;
  for (int i = 0; i < heapSize; ++i)
        array[i] = array[i+1];
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13454948
>>>> Alex, this code is wrong. it is a minHeap not a sorted array

Do you want to say that's the original code was ok?

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

0
 
LVL 9

Expert Comment

by:jhshukla
ID: 13455188
no and yes.
1. For a indexing scheme starting at 0 it is wrong. for indexing scheme starting at 1 it is right.
2. the structure is right but the details are wrong.
the author knew what was supposed to be done but not how it is to be done. (s)he attempted to use 1-based indexing in C++ and screwed everything up. and if you look at the comment right before accepted solution in the http://Q_21334130.html you can see what percolateDn() does. it re-organizes heap so that the semantics of minheap are maintained. semantics were [most likely] destroyed when the last value in the heap was moved to root position.
0
 
LVL 9

Expert Comment

by:jhshukla
ID: 13455190
how do you use that feature? was it supposed to be http:Q_21334130.html
0
 
LVL 9

Accepted Solution

by:
jhshukla earned 2000 total points
ID: 13455217
very important info for f15e. there is a bug. use
array[0] = array[--heapSize];
instead of
array[1] = array[heapSize--];

note the predecrement.
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question