# 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}*

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

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