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.
7. Return to main and display the result.
8. Exit.

advertisement
advertisement
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.