# C++ Program to Implement Heap Sort

This is a C++ program to sort the given data using Heap Sort.

Problem Description

1. Heap sort is a comparison based algorithm.
2. It is improved version of selection sort.
3. The time complexity is O(n*log(n)).

Problem Solution

1. Build a max heap using the given data element.
2. Delete the root node repeatedly.
3. Store the node at the end of the array.
4. Display the result.
5. Exit.

Program/Source Code

C++ program to implement Heap Sort.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

```#include <iostream>

using namespace std;

// A function to heapify the array.
void MaxHeapify(int a[], int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;

while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
// Break if parent value is already greater than child value.
if (temp > a[j])
break;
// Switching value with the parent node if temp < a[j].
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void HeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
// Storing maximum value at the end.
temp = a[i];
a[i] = a[1];
a[1] = temp;
// Building max heap of remaining element.
MaxHeapify(a, 1, i - 1);
}
}
void Build_MaxHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--)
MaxHeapify(a, i, n);
}
int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
n++;
int arr[n];
for(i = 1; i < n; i++)
{
cout<<"Enter element "<<i<<": ";
cin>>arr[i];
}
// Building max heap.
Build_MaxHeap(arr, n-1);
HeapSort(arr, n-1);

// Printing the sorted data.
cout<<"\nSorted Data ";

for (i = 1; i < n; i++)
cout<<"->"<<arr[i];

return 0;
}```
Program Explanation

1. Take input of data.
2. Call Build_MaxHeap() function with ‘arr’ the array of data and ‘n-1’ the number of values, in the argument list.
3. After building the max heap call HeapSort().
4. Switch the root value of heap with the last index value of array since root value is highest among all.
5. Decrement the last index value.
6. Repeat it for all the element.
8. Exit.

Runtime Test Cases
```Case 1:

Enter the number of data element to be sorted: 10
Enter element 1: 9
Enter element 2: 6
Enter element 3: 4
Enter element 4: 3
Enter element 5: 8
Enter element 6: 7
Enter element 7: 5
Enter element 8: 2
Enter element 9: 0
Enter element 10: 1

Sorted Data ->0->1->2->3->4->5->6->7->8->9```

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

If you find any mistake above, kindly email to [email protected]