C++ Program to Implement Heap Sort Algorithm

                                                   C++ Program to Implement Heap Sort


First Question comes in our mind that What is Heap Sort.?

Heap Sort - It is a algorithm , bu which we usually sort our data into a special type of tree called Binary Tree , that's what we called Heap. Here we have to arrange the data in to two Manners-

1. Max Heap
2. Min Heap

A max tree is a tree in which the key value in each node is no smaller than the key values in its children.  A max heap is a complete binary tree that is also a max tree.

A min tree is a tree in which the key value in each node is no larger than the key values in its children.  A min heap is a complete binary tree that is also a min tree.

Operations on heaps

1. Creation of an empty heap
2. Insertion of a new element into the heap;
3. Deletion of the largest element from the heap


Max Heap - Figure shows all the elements in a Max Heap

Property:
The root of max heap (min heap) contains
the largest (smallest).

Min Heap - Figure shows all the elements in a Min Heap

Example of Insertion Into Max Heap

For showing the example i am just inserting a Pic for Better understanding of the all concepts.

Here you can understand that how to insert  aelement into a Max Heap.

Steps

1. Find Initial Location of New Node

2. Insert 5 into Heap

3. Insert 21 into Heap


Example of Deletion Into Max Heap

Here is the image for removing the element from Max Heap.
Here 20 is removed  from the giving Example.








Source Code

#include
#include
using namespace std;
void insert(int a[], int n, int item);
int deleteheap(int a[],int n);
int main()
{
          int a[20],i,n,item;
          cout<<"\n enter number of elements in array";
          cin>>n;
          for(i=0;i
           {   
               cout<<"enter number::"<
               cin>>a[i];
           }
           for(i=0;i
           {   
               
               item=a[i];
               insert(a,i,item);
           } 
           cout<<"\n heap is";
           for(i=0;i
           {   
               cout<<" "<
               
           }
           
           for(i=n;i>=1;i--)
           {
                item=deleteheap(a,i);
                a[i-1]=item;                   
                              
           }
           
            cout<<"\n SORTED LIST IS!!!!\n";
           for(i=0;i
           {   
               cout<<" "<
               
           }
           getch();
           }
  void insert(int a[], int n, int item)
  {
       int ptr,par,temp;
       a[n]=item;
       ptr=n;
       par=(ptr-1)/2;
       while(ptr>=1)
       {
              if(a[par]>=a[ptr])
              break;
              else
              {
                temp=a[par];
                a[par]=a[ptr];
                a[ptr]=temp;
                ptr=par;
                par=(ptr-1)/2;
              } 
        }    
   }   
   
   int deleteheap(int a[],int n)
   {
        int i=0,item,temp;              
        item=a[0];
        a[0]=a[n-1];
        n=n-1;
        while(((a[i]
        {
              if(a[2*i+1]>a[2*i+2]) 
              {
                    temp=a[i];
                    a[i]=a[2*i+1];
                    a[2*i+1]=temp;
                    i=2*i+1;
              } 
              else 
              {
                    temp=a[i];
                    a[i]=a[2*i+2];
                    a[2*i+2]=temp;
                    i=2*i+2;
              } 
        } 
        return item;
   } 


OutPut of the Program

SHARE

Admin

• 
• 
• 
• 
•