Home > C++ > C++ Heap Sort

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:

1590101013523

 

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.

root node removed

 

 

 

 

 

 

 

 

 

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.

root replaced

 

 

 

 

 

 

 

 

 

Now again converting the tree to max heap.

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

removing root node

 

 

 

 

 

 

 

 

 

Taking the last element 5 from the tree and placing it at the root node. Also cutting the empty last node.root replaced

 

 

 

 

 

 

 

 

Again converting the tree to max heap.

converting to max heap

 

 

 

 

 

 

 

 

 

Placing the maximum value i.e. 23 to its position in the array.

removing root node

 

 

 

 

 

 

 

 

 

Taking the last value and placing it at the root node. Also cutting the last empty node.

replacing root node

 

 

 

 

 

 

 

 

 

Converting to max heap.

converting to max heap

 

 

 

 

 

 

 

 

 

Putting the maximum value in the array.

removing root node

 

 

 

 

 

 

 

 

 

Replacing the value from last node to the root node.

replacing root node

 

 

 

 

 

 

 

 

 

Converting to max heap.

converting to max heap

 

 

 

 

 

 

 

 

 

Taking the value of root node out and placing it in the array.

root removed

 

 

 

 

 

 

 

 

 

Replacing the last node. i.e. 5 to root node.

root replaced

 

 

 

 

 

 

 

 

 

As now it is in max heap position so taking the 5 out and placing it in array.

root removed

 

 

 

 

 

 

 

 

 

Now we are left with only one node so placing it in the array.

last node removed

 

 

 

 

Now as we can see in the image above our array is sorted.

Sorted array using heap sort algorithm

 

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[0], 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;
}

heap sort in c++

 

 

 

 

 

 

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[0], 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;
}

 

c++ heap sort

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

Leave a Reply

Your email address will not be published. Required fields are marked *

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