Heap Sort in C++

In this tutorial, we will be learning how to perform heap sort in C++.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

The following terms must be clear to implement heap sort in arrays:

  • Binary Tree – a data structure which consists of a parent node, followed by at most two children nodes, which themselves may be followed by at most two children nodes, each; and so on
    Note, a simple binary tree would be:
        1
      /  \
    2     3
  • Binary Heap – a binary tree in which the values at all parent nodes are greater than the values at their respective children nodes
    Note, the binary tree given above is a binary heap
  • Array representation of binary tree – if the parent node is stored at index ‘x’ of the array, then the children nodes can be stores at index ‘2x + 1’ (left child) and index ‘2x +2’ (right child)

‘Heap Sort’ uses the following algorithm to sort the elements of an array:
let the array be -> {1,4,3,2}

  1. Build a max heap in the array
    Note, the heapifying process has to be bottom-to-top as the parent node can be heapified only if the children nodes are heapified
    The array before building max-heap
    1(0)
    /   \
    4(1)  3(2)
    /
    2(3)
    The array after building max-heap
    4(0)
    /   \
    3(1)  2(2)
    /
    1(3)
  2. Largest item, which is stored at the root of the heap, is swapped with the last item of the heap and the root of the tree is heapified
    Note, the array after swapping
    1(0)
    /   \
    3(1)  2(2)
    /
    4(3)
    Note, the array after heapifying
    3(0)
    /   \
    1(1)  2(2)
    /
    4(3)
  3. Step 2 is repeated until the array size becomes 1
    Note, after step 3 is completed, the array becomes
                1(0)
             /   \
        2(1)  3(2)
       /
    4(3)

Code to perform or implement Heap Sort in C++

#include <stdio.h>
#define size 4//pre-defining the array length to be 4
void swap(int* p, int* q)//this function swaps the values to which pointers p and q point
{
    int temporary = *q;
    *q = *p;
    *p = temporary;
}
void inputArray(int array[],int length)
 {
     printf("Input %d (integer) elements: ",length);
     //note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
     for(length--;length>=0;length--){
        scanf("%d",&array[length]);
     }
 }
void printArray(int array[],int length)
 {
     printf("The elements of the given array are: ");
     for(int i=0;i<length;i++)printf("%d ",array[i]);
 }
void heapify(int array[], int length, int index) 
{ 
    int largest = index; // taking value of 'index' as root-index 
    int left = 2*index + 1;//left node of the virtual binary tree
    int right = 2*index + 2;//right node of the virtual binary tree
    if (left < length && array[left] > array[largest]) largest = left;//taking 'left' as root-index if 'array[left]' is greater 
    if (right < length && array[right] > array[largest]) largest = right;//taking 'right' as root-index if 'array[right]' is greater
    if (largest != index)//if the original root-index in the function is changed 
    { 
        swap(&array[index], &array[largest]);//swapping the value at original root-index  with that at changed root-index
        heapify(array, length, largest);//using recursion to heapify further with the changed root-index
    } 
}
void heapSort(int array[], int length) 
{ 
    int i;
    for (i = length / 2 - 1; i >= 0; i--) heapify(array, length, i); //building the heap in array
    for (i=length-1; i>=0; i--)//extracting elements from heap
    { 
        swap(&array[0], &array[i]);//swapping value at current-root with the value at end
        heapify(array, i, 0);//heapifying
    } 
} 
int main()
{
    int array[size];
    inputArray(array,size);
    heapSort(array,size);
    printArray(array,size);
    return 0;
}

Output:

Input 4 (integer) elements: 1 4 3 2
The elements of the given array are: 1 2 3 4

Summary of heap sort program in C++

The execution of the program is explained below:

  • inputArray(int[],int) is called to take input integer elements from the user and store them in the array
  • heapSort(int[],int,int) is called to sort the elements of the array with the algorithm explained above
  • printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

  • the value ‘4’ after size can be changed to any other value in order to get the desired array-length
  • since (in C++) arrays are passed by reference, therefore the changes made in heapSort(int[],int,int) and heapify(int[],int,int) stay permanently
  • to sort in descending order, just change the sign from ‘>’ to ‘<‘ in the inequality after && in the first two logical conditions of heapify(int[],int,int,int)

Also read:

Leave a Reply

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