Heap Sort In C++

We use recursion to perform heap sort, firstly we heapify to create a min or max Heap to perform Descending or Ascending order of sorting, depending on the requirement.

In this article we are going to sort the given array in ascending order, so we have to perform max heapify operation. Once that is done we swap the current index element with the top element, and repeat the process until the entire array is sorted.

Time Complexity of Heap Sort is O( Log(n) ).

Code For Heap Sort In C++

#include<iostream>

using namespace std;

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

{

        int Largest = i;

        int l = 2 * i + 1;   

        int r = 2 * i + 2;

        if(l<n && arr[l] > arr[largest])

         largest = l;

        if(r<n && arr[r] > arr[largest])

         largest = r;

        if(largest != i)

        {

                swap(arr[i] , arr[largest]);

                heapify(arr , n , largest);

        }

}

// void heapify...

void HeapSort(int arr[] , int n)

{

        for(int i = n / 2  - 1 ; i <= n ; i++)

        {

                heapify( arr , n , i );

        }

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

        {

                swap( arr[0] , arr[i]);

                heapify(arr , i , 0);

        }

}

// void HeapSort...

void showArr(int arr[] , int size)

{

        for(int i = 0 ; i < size; i++)

        {

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

        }

cout<<endl;

}

// void showArr...

int main()

{

       int arr[] = {3 , 4 , 5 , 2 , 1 , 6 };

       int size = sizeof(arr) / sizeof(*arr);

        HeapSort(arr,size);

        showArr( arr , size );

return 0;

}

// int main...

Output for Heap Sort In C++

1  2  3  4  5  6