{"post":"

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\n#include <iostream>
\nusing namespace std;
\nvoid create_heap(int list[], int n, int root)
\n{
\n   int largest = root; 
\n   int l = 2root + 1; // left = 2root + 1
\n   int r = 2root + 2; // right = 2root + 2
\n  
\n   if (l < n && list[l] > list[largest])
\n   largest = l;
\n  
\n   if (r < n && list[r] > list[largest])
\n   largest = r;
\n  
\n   if (largest != root)
\n      {
\n      swap(list[root], list[largest]);
\n      create_heap(list, n, largest);
\n      }
\n}
\n  
\nvoid heapSort(int list[], int n)
\n{
\n   
\n   for (int i = n / 2 - 1; i >= 0; i--)
\n   create_heap(list, n, i);
\n  
\n   for (int i=n-1; i>=0; i--)
\n   {
\n     
\n      swap(list[0], list[i]);
\n     create_heap(list, i, 0);\n   }
\n}
\n  
\nvoid displayArray(int list[], int n)
\n{
\n   for (int i=0; i<n; ++i)
\n   cout << list[i] << \" \";
\n   cout << \"\\n\";
\n}
\n  
\n// main program
\nint main()
\n{
\n   int heap_list[] = {4,17,3,12,9,6};
\n   int n = sizeof(heap_list)/sizeof(heap_list[0]);
\n   cout<<\"Input Array\"<<endl;
\n   displayArray(heap_list,n);
\n  
\n   heapSort(heap_list, n);
\n  
\n   cout << \"Sorted Array\"<<endl;
\n   displayArray(heap_list, n);
\n}

\n","title":"Heap Sort","authorDetails":{"name":"Sonal Moga","slug":"sonal-moga"},"description":null,"slug":"data-structure/heap-sort/","articleId":"636a83417bb1ce5072622b2e","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}