C++: Implementation of Heapsort (Sorting)

I have written this code after studying Heapsort algorithm from Introduction to Algorithm

max_heapify() functionThe running time of this procedure is 
O(lg n) and it helps to maintain the max-heap property. Max-heap property means every node other than root node must be smaller than or equal to its parent.

build_max_heap() function: Its running time is O(n lg n).
Result after execution of build_max_heap() function is

heap_sort function: Its running time is O(n lg n).
Result after excution of heap_sort()is


#include <iostream>

 void max_heapify(int arr[], int i, int si)
 {
   int largest, l = (2*i) + 1, r = l + 1;


   if(l < si && arr[l] > arr[i])
      largest = l;
   else
    largest = i;

   if(r < si && arr[r] > arr[largest])
    largest = r;

   if(largest != i)
   {
      int temp = arr[i];
      arr[i] = arr[largest];
      arr[largest] = temp;
      max_heapify(arr, largest, si);
   }
  }

 void build_max_heap(int arr[], int si)
 {
   for(int i = (si/2) - 1; i >= 0; i--)
    max_heapify(arr, i, si);
 }

 void heap_sort(int arr[], int si)
 {
   build_max_heap(arr, si);
   int sz = si;
   for(int i = si - 1;i > 0; i--)
   {
      int temp = arr[i];
      arr[i]   = arr[0];
      arr[0]   = temp;
      sz--;
      max_heapify(arr, 0, sz);
    }
 }

 int main()
 {
    int a[10] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    int s = sizeof(a)/sizeof(int);
    heap_sort(a, s);
    for(int i = 0;i < s; i++){
    std::cout << a[i] << " ";
 }
    return 0;
}


You can download this code from here.

Now you can understand Maximum priority Queue using Heap.





                                                                  
                                                                  
You may also like:
 C++: Huffman Coding using STL
C++: Implementation of Quicksort
C++: Insertion Sort using STL (Sorting)
C++: Implementation of Stack using Array
What programming languages do what?

Popular Posts

Top 10 Web Sites Every Programmer Should Visit Daily

C++: Huffman Coding using STL

What is "namespace" and why do we use it?