C++ program for heap sort

C++ program for heap sort

#include <iostream>

#include <iomanip>

using namespace std;

int left(int i)

{

      return 2*i+1;

}

int right(int i)

{

      return 2*i+2;

}

void minheapify(int arr[], int n, int i)

{

      int l, r,smallest,temp;

      l = left(i);

      r = right(i);

      if(l<n && arr[l] < arr[i])

            smallest = l;

      else

            smallest = i;

      if(r<n && arr[r] < arr[smallest])

            smallest = r;

      if(smallest != i)

      {

            temp = arr[i];

            arr[i] = arr[smallest];

            arr[smallest] = temp;

            minheapify(arr,n,smallest);

      }

}

void heapSort(int arr[], int n)

{

      int i,temp;

      for (i = n / 2 - 1; i >= 0; i--)

            minheapify(arr, n, i);

      for (i=n-1; i>=0; i--)

      {

            temp=arr[0];

            arr[0]=arr[i];

            arr[i]=temp;

            minheapify(arr, i, 0);

      }

}

int main()

{

      int arr[20];

      int i=0,n;

      cout<<"Enter the size of array : ";

      cin>>n;

      cout<<"\nEnter the elements : ";

      for(i=0;i<n;i++)

            cin>>arr[i];

      for(i=(n-1)/2;i>=0;i--)

            minheapify(arr,n,i);

      cout<<"\nArray after Minheap \n";

      for(i=0;i<n;i++)

            cout<<arr[i]<<"  ";

      heapSort(arr, n);

      cout<<"\nArray after Heap sort \n";

            for(i=n-1;i>=0;i--)

                  cout<<arr[i]<<"  ";

      return 0;

}

 Output

Enter the size of array : 7

Enter the elements : 48

0

-1

82

10

2

100

Array after Minheap

-1  0  2  82  10  48  100 

Array after Heap sort

-1  0  2  10  48  82  100