Binary Heap Problem 92

Back to Problem Solutions forum

Igor Shapovalov     2020-10-18 20:24:53

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;
            }
Igor Shapovalov     2020-10-18 20:37:44

I passed it but I still can't understand why does it work once in a while

Please login and solve 5 problems to be able to post at forum