### C++: Implementation of Heapsort (Sorting)

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){

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()**function: The 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?**