C++: Implementation of Heapsort (Sorting)

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

1. #include <iostream>

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


4. if(l<si&&arr[l]>arr[i])
5.    largest=l;
6. else
7.    largest=i;

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

10. if(largest!=i){
11.    int temp=arr[i];
12.    arr[i]=arr[largest];
13.    arr[largest]=temp;
14.    max_heapify(arr,largest,si);
15.}
16.}

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

21. void heap_sort(int arr[],int si){
22. build_max_heap(arr,si);
23. int sz=si;
24. for(int i=si-1;i>0;i--){
25.    int temp=arr[i];
27.    arr[i]=arr[0];
28.    arr[0]=temp;
29.    sz--;
30.    max_heapify(arr,0,sz);
31.    }
32. }

33. int main()
34. {
35.    int a[10]={4,1,3,2,16,9,10,14,8,7};
36.    int s=sizeof(a)/sizeof(int);
37.    heap_sort(a,s);
38.    for(int i=0;i<s;i++){
39.    std::cout<<a[i]<<" ";
40. }
41.    return 0;
42. }

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(nlgn).
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

Reference:


You may also like:
C++: Implementation of Quicksort
C++: Merge_Sort using Vector
C++: Insertion Sort
C++: Implementation of Stack using Array
What programming languages do what?

Popular Posts

Top 10 Web Sites Every Programmer Should Visit Daily

How do I improve my logical thinking and problem solving skills?

C++: STL Iterators