Heap Sort in C++

Introduction to Heap Sort in C++

Heapsort is one of the comparison-based sorting techniques and is part of the selection sort. The heapsort technique uses a comparison mechanism based on the Binary Heap data structure. In this technique, first, choose a maximum element and place the maximum element at the end. The same process is repeated for the remaining elements. There are many different techniques involved in sorting each having their respective efficiency in the time taken to sort the given data and requirement of space in memory. They are bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort.

What is Heap Sort?

Heapsort is a sorting approach based on the binary heap data structure similar to selection sort where we first obtain the maximal piece of data set and place it at the end and continue for the rest of the elements.

Heapsort as the name itself suggests. It first builds the heap of data elements from the given unsorted array, and then checks for the largest item and places it at the end of the partly sorted array. It again rebuilds the heap, searches for the next largest piece of record and places it in the next empty slot from the end of the half sorted arrangement of records. This process is repeated until no items left in the heap. This technique requires two arrays one for storing the heap and the other for a sorted array.

Algorithm of Heap Sort in C++

• Firstly choose root as an elevated element from the given information set of elements to create a maximal heap.
• Reconstruct the heap by placing or interchanging the root with the last element.
• The heap size will now shrink by 1.
• Then we again make the heap with remaining elements and continue until the heap size is reduced to 1.

Example of Heap Sort in C++

This technique uses binary heap which is constructed using a complete binary tree where the root node is greater than its two children nodes.

Consider the given array of data sets.

Let us go according to the algorithm. It says to select the highest element as the root and construct the maximal heap.

1. First Iteration

Now the array will be of the form:

Now the sorted array will be of the form:

The heap size will be reduced by 1, now 6-1 = 5.

2. Second Iteration

So now the heap looks like:

The array is of the form:

The sorted array will be:

The heap size will be reduced by 1, now 5-1 = 4.

3. Third Iteration

The new heap looks like:

The array is of the form:

The sorted array will be:

The heap size will be reduced by 1, now 4-1 = 3.

4. Fourth Iteration

The new heap looks like:

The array is of the form:

The sorted array will be:

 
The heap size will be reduced by 1, now 3-1 = 2.

5. Fifth Iteration

The new heap looks like:

The array is of the form:

The sorted array will be:

The heap size will be reduced by 1, now 2-1 = 1.

6. Last Iteration

The new heap looks like:

The array has:

4 

From the algorithm, we have carried out all the steps until the heap size is 1. So we now have the sorted array:

 
Therefore the sorted array of the maximal heap is in ascending order. If we need the array sorted in descending order then follow the above steps with a minimal heap.

C++ program for heap sort is as given below:

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int arr[] = { 5,18,4,13,10,7};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}

Output:

Conclusion

Heapsort is the comparison based technique which is the enhancement of selection sorting. Heap sort makes use of selecting the highest or lowest element in the given array to sort in ascending or descending order respectively with the maximal or minimal heap. Carry out this process until we get one as heap size. This sorting technique is also used to find the greatest and lowest element in the array. The heap sort technique is more efficient and faster than the selection sort technique.

Recommended Articles

This is a guide to Heap Sort in C++. Here we discuss what is heap sort in c++, working with its algorithm and Example. You may also look at the following articles to learn more-

1. Heap Sort in C
2. Heap Sort In Java
3. Overloading in C++
4. Pointers in C++