Heap Sort

Heapsort is a comparison-based sort method and belongs to the selection sort family. Heapsort can be a little slower algorithm when compared with quicksort but can still be better than worst-case O(n Log n) runtime. It is an in-place algorithm but the algorithm is not as stable as merge & quick sort.

It is a binary heap data structure, it is similar to selection sort as it also recognizes the largest element first and puts at the end of the array and repeats the algorithm till all the elements are sorted.

Let us take an example: 8, 10, 5, 12, and 14

Code:

//Program to show heap sort
#include <iostream>
using namespace std;
void create_heap(int list[], int n, int root)
{
   int largest = root; 
   int l = 2root + 1; // left = 2root + 1
   int r = 2root + 2; // right = 2root + 2
  
   if (l < n && list[l] > list[largest])
   largest = l;
  
   if (r < n && list[r] > list[largest])
   largest = r;
  
   if (largest != root)
      {
      swap(list[root], list[largest]);
      create_heap(list, n, largest);
      }
}
  
void heapSort(int list[], int n)
{
   
   for (int i = n / 2 - 1; i >= 0; i--)
   create_heap(list, n, i);
  
   for (int i=n-1; i>=0; i--)
   {
     
      swap(list[0], list[i]);
     create_heap(list, i, 0);
   }
}
  
void displayArray(int list[], int n)
{
   for (int i=0; i<n; ++i)
   cout << list[i] << " ";
   cout << "\n";
}
  
// main program
int main()
{
   int heap_list[] = {4,17,3,12,9,6};
   int n = sizeof(heap_list)/sizeof(heap_list[0]);
   cout<<"Input Array"<<endl;
   displayArray(heap_list,n);
  
   heapSort(heap_list, n);
  
   cout << "Sorted Array"<<endl;
   displayArray(heap_list, n);
}