Heap Sort

/*********************************************************

-> This program is to perform heap sort.

-> This program works in microsoft vc++ 6.0 environment

**********************************************************/

#include<iostream.h>
#include<stdlib.h>

class sorting
{
private:
 int n,size;
 double *minheap;
public:
 void insert_minheap(double);
 double delete_one_minheap();
 void input();
 void output();
};
void sorting::insert_minheap(double n)
{
 if(size>=9)
 {
  cout<<”array overflow “;
  exit(0);
 }
    minheap[++size]=n;
    //Reorder the heap
    int k=size;
    while(k>1)            //k has a parent
    {
            if(minheap[k]<minheap[k/2])
            {
                    double t=minheap[k];
                    minheap[k]=minheap[k/2];
                    minheap[k/2]=t;
                   
                     k/=2;
            }
            else
                    break;
    }
}

double sorting::delete_one_minheap()
{
    if(size<1)
            return -1;
 double val;
    val=minheap[1];
    minheap[1]=minheap[size];
    size–;
   
    //Reorder the heap by moving down
    int k=1;
    int newk;
    while(2*k<=size)     //k has atleast one chaild
    {
            //Set newk to the index of the smallest chaild of k
            if(2*k==size)     //if k has only left chaid
            {
    newk=2*k;
            }
            else                //k has two chailds
            {
                if(minheap[2*k]<minheap[2*k+1])
                        newk=2*k;
                else
                        newk=2*k+1;
            }
            if(minheap[k]<minheap[newk])
                    break;
            else
            {
                    double t;
                    t=minheap[k];
                    minheap[k]=minheap[newk];
                    minheap[newk]=t;
                   
                    k=newk;
            }
    }
    return val;
}

void sorting::input()
{
 cout<<”****************************************************\n”
  <<”This program sorts numbers in increasing order”
  <<”\n\t\tusing heap sort technique\n”
  <<”****************************************************\n”;

 cout<<”Enter how many numbers you are going to enter for sorting ::”;
 cin>>n;
 minheap=new double[n+1];

 /********** Construct a heap with the input elements *******/

 size=0;
 cout<<”Now enter the elements\n”;
 double number;
    for(int i=1;i<=n;i++)
 {
  cin>>number;
  insert_minheap(number);
 }
}

void sorting::output()
{
 cout<<”The sorted numbers are ::\n”;
 for(int i=1;i<=n;i++)
  cout<<delete_one_minheap()<<’\t’;
 cout<<endl;
}
int main()
{
 sorting obj;
 obj.input();
 obj.output();
 return 0;
}
/************************************************************************

SAMPLE OUTPUT ::

****************************************************
This program sorts numbers in increasing order
                using heap sort technique
****************************************************
Enter how many numbers you are going to enter for sorting ::7
Now enter the elements
1.7
1.6
1.5
1.4
1.3
1.2
1.1
The sorted numbers are ::
1.1     1.2     1.3     1.4     1.5     1.6     1.7
Press any key to continue

************************************************************************/