C++ Programming Code Examples C++ > Sorting Searching Code Examples C++ Program to Implement Heap Sort C++ Program to Implement Heap Sort This is a C++ program to sort the given data using Heap Sort. - Heap sort is a comparison based algorithm. - It is improved version of selection sort. - The time complexity is O(n*log(n)). - Build a max heap using the given data element. - Delete the root node repeatedly. - Store the node at the end of the array. - Display the result. - Exit. #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; }