While inserting nodes in heap how to use bubble up?
Following is my code which doesnot properl开发者_如何学JAVAy bubbles up the larger value .Can any one help out .The problem is somewhat at count++ .
#include<iostream>
using namespace std;
class heap{
public:
int count;
heap(int c)
{
count=c;
}
int Arr[10];
void insert(int num);
void deletemax();
void print();
};
void heap::insert(int num){
if(count==10){
cout<<"Heap full\n";
exit(1);
}
else{
Arr[count]=num;
count++; //The real problem arises here that the compiler adds 1 to count and when the code moves ahead it sets position var to count++ value and tries to compare a value at Arr[POS] with its parent whereas there is no value at this place set uptill.
}
int POS=count;
while(Arr[POS]>Arr[(POS-1)/2]){
int temp;
temp=Arr[POS];
Arr[(POS-1)/2]=temp;
POS=(POS-1)/2;
}
}
void heap::print(){
for(int i=0; i<10; i++){
cout<<Arr[i]<<endl;
}
}
int main(){
heap h(0);
int a;
int b=0;
while(b<10){
cout<<"Insert node in heap\n";
cin>>a;
h.insert(a);
b++;
}
h.print();
return 0;
}
I would agree, that's where your problem is.
There are many issues with the code you posted, some of which include:
- As to your specific issue, I would guess you need to change the line in heap::insert() to "int POS=count-1;" to properly start iterating from the back of the array.
- You need to consider the case of adding an element to an empty array and what then happens in your sorting code.
- Your constructor allows someone to create a heap that will overflow the fixed sized array, for example heap(1000). In addition, the Arr member is not initialized which means it has undefined data for any value but heap(0). In this case your constructor should not take any parameters and count should just be initialized to 0.
- The purpose of the code is confusing. Is it a heap, a sorted array, an attempt to approximate a heap with an array, none of the above? If you are simply trying to implement a fixed sized sorted array then I believe your sorting code in insert() will not work (e.g., consider adding 100 to a heap containing [1,2,3]).
There are other, more basic things, wrong (like not using any the STL containers, public class member, non-const parameter passing, "using std", etc...) but I'm assuming you are merely experimenting/playing here.
精彩评论