C++ Heap Sort is a sorting method based on comparisons between the elements. The heapsort is a comparison-based sorting technique based on a Binary Heap data structure. The sorting method works on the principle of binary heap data structure.

The binary heap data structure is much similar to the binary tree. A binary heap is a tree in which the elements are stored in a particular tree-like structure. In this, the parent node is either greater (or smaller) than the values stored in the child nodes. Accordingly, the heaps are either called max heap or min-heap, respectively.

The blog has already covered QuickSort, MergeSort, and BubbleSort in C++ in this blog.

**C++ Heap Sort**

Heapsort is similar to the selection sort, where we first find the maximum element and place a maximum element at the end. We repeat the same process for the remaining item.

In this, the largest element among the values is selected and then placed at the end of the value list (in case of ascending order sorting).

**What is a Binary Heap**

The complete binary tree is a binary tree in which every level, except possibly the last, is filled, and all nodes are as far left as possible.

The Binary Heap is a Complete Binary Tree where elements are stored in a unique order such that the value in the parent node is greater(or smaller) than the values in its two children nodes.

The former is called max heap, and the latter is called min-heap. The binary tree or array can represent the heap.

**Reasons for using Array Data Structure**

In this sorting method, we use array data structures. It is mainly due to two significant reasons :

- Array data structures are quite fast and space-efficient. Since the elements are stored in contiguous memory blocks in array data structures, we don’t have to store the memory addresses of every element. It thereby decreases the space required for storing the same number of items compared to other data structures.
- Arrays are also used here because it gets too easy to access the child nodes if the address of the parent node is known. Let us say if the parent node is stored at an index “z” in the array, and then the child nodes will automatically be stored at 2*z+1 (for the left node) and 2*z+2 (for the right node). This isn’t the case with other data structures, where it becomes quite challenging to find the child nodes.

**Algorithm for Heap Sort Method**

- Once the user has entered the values to be sorted, they are added to an array data structure. After the values have been stored, the instructions are given to make the maximum heap out of those elements.
- This makes the largest element to be stored at the root position of the heap. After this, the size of the heap is reduced by 1, and the last element of the heap replace the value at the root position.
- Finally, the root position of the heap is heaped. This is done following the following procedure:
- The heapification procedure is performed from bottom to up order because a node can be heaped only if the values under it are heapify.
- Take an example for the values: 12, 20, 6, 15, 2

12(0)

/ \

20(1) 6(2)

/ \

15(3) 2(4)

**Starting the procedure with index 1:**

12(0)

/ \

20(1) 6(2)

/ \

15(3) 2(4)

**Then we are continuing with index 0:**

20(0)

/ \

15(1) 6(2)

/ \

12(3) 2(4)

The above steps are repeated repeatedly until the value of the heap is greater than 1.

**C++ Heap Sort Program**

See the following program.

#include <iostream> using namespace std; void convertHeap(int array[], int len, int x) { int largest = x; int left = 2 * x + 1; int right = 2 * x + 2; if (left < len && array[left] > array[largest]) largest = left; if (right < len && array[right] > array[largest]) largest = right; if (largest != x) { swap(array[x], array[largest]); convertHeap(array, len, largest); } } void heapSort(int array[], int len) { for (int i = len / 2 - 1; i >= 0; i--) convertHeap(array, len, i); for (int i = len - 1; i >= 0; i--) { swap(array[0], array[i]); convertHeap(array, i, 0); } } void display(int array[], int len) { cout << "After sorting, the array is: \n"; for (int i = 0; i < len; ++i) cout << array[i] << " "; cout << endl; } int main() { int array[] = {12, 20, 6, 15, 2}; int len = sizeof(array) / sizeof(array[0]); heapSort(array, len); display(array, len); }

That’s it for this tutorial.