Heapsort using Priority queue C++

Question

My code works for putting data into the array but when I print it out, it always crashes after first number. There must be something wrong with my bubbledown function, could you point out what is wrong with it? Thank you in advance.

#include<iostream>
#include <string>
#include<fstream>
using namespace std;

void bubbleup(int pq[], int back);
void bubbledown(int pq[], int front, int back);
void swap(int &a, int &b);

int main(){
    ifstream infile;
    ofstream outfile;
    string input, output;
    int size,number;
    int front=1, back=0;
    int *pq=new int[size]; // dynamically allocate array
    cout<<"What's the input file name?"<<endl;
    getline(cin, input); // get the input name
    infile.open(input.c_str());// open the input file

    while(!(infile.eof())){
      infile>>number; // infile to an integer type variable first instead of an array. this is why your program doesn't work!!!!!
      back++;
      pq[back]=number;
      bubbleup(pq,back);
      for(int i=1;i<=back;i++)
        cout<<pq[i]<<" ";
      cout<<endl;
    }
    cout<<"what's the output file name?"<<endl;
    getline(cin, output);
    outfile.open(output.c_str());
    while(back!=0){
        cout<< pq[front]<<endl;
        outfile<< pq[front]<<endl;
        pq[front]=pq[back];
        back--;
        bubbledown(pq,front,back);
    }
}
//bubbleup function
void bubbleup(int pq[], int back)
{
     int fatherindex=back/2;
        while(!(pq[back]>=pq[fatherindex])||!(back==1)){

          if(pq[back]<pq[fatherindex])
           swap(pq[back],pq[fatherindex]);
           back=fatherindex;
           fatherindex=back/2;
        }   
}

//bubbledown function
void bubbledown(int pq[], int front, int back){
    int fatherindex=front,kidindex;
    while(2*fatherindex+1 <= back){
        kidindex=2*fatherindex+1;
        if((kidindex+1<back) && (pq[kidindex]<pq[kidindex+1])){
           kidindex++;
           }
        if(pq[fatherindex] > pq[kidindex]){
           swap(pq[fatherindex],pq[kidindex]);
           fatherindex=kidindex;
        }
        else
          return;
    }
}
//swap function
void swap(int &a, int &b){
    int t=a;
        a=b;
        b=t;
}

Possible duplicate of http://stackoverflow.com/q/23139648/2724703 — Mantosh Kumar, Apr 29 '14 at 01:36
while (!infile.eof()) is not the correct way to check the end of file. Please refer the above question post to understand it completely. — Mantosh Kumar, Apr 29 '14 at 01:38

The Dark · Answer 1 · 2014-04-29T02:24:25.407

0

A few problems to look at

You don't initialize size before using it, so your pq memory could be any size at all.
You are using 1-based access to your arrays, so make sure you allocate one more than you need.
while(!back==0) will work, but it is doing boolean logic on an int, then comparing the result with an int. while(back!=0) is a lot easier to read and will produce fewer compiler warnings.

Edit: also your bubbleDown function has an infinite loop when neither if test is triggered.

edited Apr 29 '14 at 02:24

answered Apr 29 '14 at 02:19

The Dark

8,453
1
16
19

Thank you! I made some changes, it runs now, but does not print out the correct data. Could you read for my code again? – user2836989 Apr 29 '14 at 02:45
@user2836989: Stack Overflow is not a debugging service. You can't just ask for somebody to find the errors in your code. – Greg Hewgill Apr 29 '14 at 03:03

Heapsort using Priority queue C++

1 Answers1