C++ Heap Sort

Heap sort is a comparison based technique which we can use to sort the array. This algorithm uses Heap data structure for sorting particularly binary heap. Somehow heap sort algorithm resembles selection sort. Where we choose the maximum value element and place it at the end and then the next maximum element and so on. We can say that it is an improved version of selection sort.

The concept of binary heap arises from complete binary tree. We can define the binary heap as the complete binary tree in which we store the items in a special order such as: each parent node has the maximum value than any of its child, we call this as the max heap and if each parent node has the value smaller than its children we call it as the min heap.

We can store binary heap in an array and if we store the parent node at an index i of the array then we can obtain the left child by 2*i+1 and the right child by 2* i+2.

Heap Sort Algorithm

For Ascending Order

•  1. Create the max heap for input data.
•  2. Since we store the largest item at the root node of the heap in max heap. So replace it with the last item            of the heap following by reducing the size of heap by 1. i.e. remove the largest element from the tree.
•  3. Finally, heapify the root of tree. i.e. Again create the max heap.
•  4. Repeat above steps unless all the elements of the array are sorted.

For Descending Order

•  1. Create the min heap for input data.
•  2. Since we store the smallest item at the root node of the heap in min heap. So replace it with the last item          of the heap following by reducing the size of heap by 1. i.e. remove the smallest element from the tree.
•  3. Finally, heapify the root of tree. i.e. Again create the max heap.
•  4. Repeat above steps unless all the elements of the array are sorted.

Creating a binary tree from an unsorted array

For example, if we have an array like:

 15 90 10 101 3 5 23

We can create a binary tree from the above data as:

And for the above array we have max and min heap as:

What is Heapify?

We can define heapify as the process of converting a binary tree into a Heap. Simply we can demonstrate the working of heapify by the following pseudo code.

heapify(my_array)

root_node = my_array [i] // for root node i =0

largest_Element = largest( my_array [i] , my_array [2*i + 1]. my_array [2*i+2]) //this will give us the largest value from root and its both children.

if(root_node!= largest_Element)

Swap(root_node, largest_Element)

Heapify is a recursive process.

Here is the C++ code for heapify function.

```void heapify(int my_arr[], int n, int i)
{
int largest = i;
int l_child = 2 * i + 1;
int r_child = 2 * i + 2;
if (l_child < n && my_arr[l_child] > my_arr[largest])
{
largest = l_child;
}
if (r_child < n && my_arr[r_child] > my_arr[largest])
{
largest = r_child;
}
if (largest != i)
{
swap(my_arr[i], my_arr[largest]);
heapify(my_arr, n, largest);
}
}```

Creating the Sorted Array from Max Heap

We can sort the array in ascending order from max heap by following these steps:

•  1. When the tree is satisfying the max heap property. The very largest value is at the root node of the tree.
•  2. Remove the value from the root node and place it at the last index of the array. (in each iteration we                   decrease the index of array by 1)
•  3. Take the value of the last node and then place it at the root node. And remove the empty last node.
•  4. Again convert the tree to max heap.
•  5. Repeat from step 1 to 4 until all the values of the array are sorted.

Here is an example of sorting the array in ascending order.

Taking the largest element from the root node and placing it at the end of the array. Now as the root node is empty we take value of the last node i.e. 10 and place it at the root node. And cutting the last empty node. Now again converting the tree to max heap. Again taking the value from root node and placing it in the array. This time as mentioned above we reduce the index by 1. Taking the last element 5 from the tree and placing it at the root node. Also cutting the empty last node. Again converting the tree to max heap. Placing the maximum value i.e. 23 to its position in the array. Taking the last value and placing it at the root node. Also cutting the last empty node. Converting to max heap. Putting the maximum value in the array. Replacing the value from last node to the root node. Converting to max heap. Taking the value of root node out and placing it in the array. Replacing the last node. i.e. 5 to root node. As now it is in max heap position so taking the 5 out and placing it in array. Now we are left with only one node so placing it in the array. Now as we can see in the image above our array is sorted. Heap Sort in C++ Code

```#include "stdafx.h"
#include "iostream"

void heapify(int my_arr[], int , int );
void heapSort(int my_arr[], int );
void display(int my_arr[], int );

using namespace std;
int main()
{
int *my_arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
my_arr = new int[size];
cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index " << i + 1 << " : ";
cin >> my_arr[i];
}
cout << "Unsorted array is \n";
display(my_arr, size);
heapSort(my_arr, size);
cout << "Sorted array using heap sort is \n";
display(my_arr, size);
}
void heapify(int my_arr[], int n, int i)
{
int largest = i;
int l_child = 2 * i + 1;
int r_child = 2 * i + 2;
if (l_child < n && my_arr[l_child] > my_arr[largest])
{
largest = l_child;
}
if (r_child < n && my_arr[r_child] > my_arr[largest])
{
largest = r_child;
}
if (largest != i)
{
swap(my_arr[i], my_arr[largest]);
heapify(my_arr, n, largest);
}
}
void heapSort(int my_arr[], int n)
{
// Building the max heap
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify(my_arr, n, i);
}
//Sorting
for (int i = n - 1; i >= 0; i--)
{
swap(my_arr, my_arr[i]);
heapify(my_arr, i, 0);
}
}
void display(int my_arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
cout << my_arr[i] << "  ";
}
cout << endl;
}
``` Similarly, we can sort the array in descending order as well from max heap by following these steps:

•  1. When the tree is satisfying the max heap property. The very smallest value is at the root node of the tree.
•  2. Remove the value from the root node and place it at the 1st index of the array. (In each iteration increase          the index of array by 1).
•  3. Take the value of the last node and then place it at the root node. And remove the empty last node.
•  4. Again convert the tree to max heap.
•  5. Repeat from step 1 to 4 until all the values of the array are sorted.

C++ code for Sorting array in Descending order

```#include "stdafx.h"
#include "iostream"

void heapify(int my_arr[], int , int );
void heapSort(int my_arr[], int );
void display(int my_arr[], int );

using namespace std;
int main()
{
int *my_arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
my_arr = new int[size];
cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index " << i + 1 << " : ";
cin >> my_arr[i];
}
cout << "Unsorted array is \n";
display(my_arr, size);
heapSort(my_arr, size);
cout << "Sorted array using heap sort is \n";
display(my_arr, size);
}
void heapify(int my_arr[], int n, int i)
{
int largest = i;
int l_child = 2 * i + 1;
int r_child = 2 * i + 2;
if (l_child < n && my_arr[l_child] < my_arr[largest])
{
largest = l_child;
}
if (r_child < n && my_arr[r_child] < my_arr[largest])
{
largest = r_child;
}
if (largest != i)
{
swap(my_arr[i], my_arr[largest]);
heapify(my_arr, n, largest);
}
}
void heapSort(int my_arr[], int n)
{
// Building the max heap
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify(my_arr, n, i);
}
//Sorting the array
for (int i = n - 1; i >= 0; i--)
{
swap(my_arr, my_arr[i]);
heapify(my_arr, i, 0);
}
}
void display(int my_arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
cout << my_arr[i] << "  ";
}
cout << endl;
}``` Time Complexity

The time complexity for heap sort remains same for each of its cases (i.e. Best, Worst and Average case.). Its time complexity is O(nlogn).

This site uses Akismet to reduce spam. Learn how your comment data is processed.