Back to Problem Solutions forum
Guys, help me pls. I can't understand my mistake, I do all by instructions from https://www.codeabbey.com/index/wiki/binary-heap. I know that InsertHelper works uncorrect because sometimes he take index less than correct parent index. What do I have to do?
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
class BinaryHeep{
private:
vector <int> heep;
void InsertHelper(int index){
if(index!=0)
if(heep[(index-1)/2]>heep[index]){
swap(heep[(index-1)/2],heep[index]);
InsertHelper((index-1)/2);
}
else
return;
}
void DeleteHelper(int index){
int temp=index;
if(2*index+1<heep.size()){
if(heep[2*index+1]<heep[index])
temp=2*index+1;
}
if(2*index+2<heep.size()){
if(heep[2*index+2]<heep[temp])
temp=2*index+2;
}
if(temp!=index){
swap(heep[index],heep[temp]);
DeleteHelper(temp);
}
}
public:
void InsertNode(int data){
if(data==0){
int temp;
temp=heep[0];
swap(heep[0],heep[heep.size()-1]);
heep.erase(heep.end()-1);
DeleteHelper(0);
}
else{
heep.push_back(data);
InsertHelper(heep.size()-1);
}
}
void Print(){
for(auto i:heep)
cout<<i<<" ";
}
};
int main()
{
int numOfInputs;
cin>>numOfInputs;
BinaryHeep heep;
for(int i=0;i<numOfInputs;i++){
int data;
cin>>data;
heep.InsertNode(data);
}
heep.Print();
return 0;
}
I passed it but I still can't understand why does it work once in a while