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

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

5 thoughts on “Heap Sort”

  1. try dis—
    #include
    #include
    using namespace std;
    #define MAX 25
    int *ar;
    int count;
    void makeheap(int *p,int count)
    {
    int i,k;

    for(i=count/2;i>=1;i–)
    {
    int val=p[i];
    int j=i;
    while(j<=count/2)
    {
    k=2*i;
    if(kar[k+1]))
    k++;
    if(p[i]<ar[k])
    {
    p[i]=ar[k];
    ar[k]=val;
    }
    else
    break;
    j=k;
    }

    }
    }
    void rearrange()
    {
    extern int count;
    int j=count,i,temp;
    while(j<=count)
    {
    i=count/2;
    if(ar[i]MAX)
    {
    cout<<"cant be added";
    return;
    }
    count++;
    ar[count]=val;
    rearrange();

    }

    void display()
    {
    int i;
    extern int count;
    // count=10;
    cout<<"display count"<<count<<endl;
    for(i=1;i<=count;i++)
    cout<<ar[i]<<endl;
    }
    void delete1()
    {
    int val=ar[1];
    ar[1]=count;
    ar[count]=val;
    count–;
    j=1;
    while(j<=count)
    {
    i=2*j;
    if(i<=count&&(ar[i]<ar[i+1]))
    i++;
    if(val<ar[i])
    {
    temp=ar[i];
    ar[i]=ar[j];
    ar[j]=temp;
    }
    else
    break;
    }
    }

    int main()
    {
    extern int count;
    extern int *ar;
    ar=new int[MAX];

    for(int i=1;i>ar[i];

    count=15;
    makeheap(ar,count);
    display();
    int c;
    cin>>c;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s