A heap is a tree-based data structure in which the tree is almost a complete binary tree. The maximum number of a child node in a binary heap is at most 2.

## Implement a Heap Sort Function using C++

In a binary heap, the height of a heap tree is `log2N`

if the heap is a complete binary tree of N nodes.

If a complete binary tree with n nodes is represented using an array, then for any node with index I, 1<=i<=n, we can access the nodes using the following formulas.

Left child of i node = 2i

Right child of i node = 2i + 1

Max-heap is a property of heap that ensures that for every node i, other than the root,

Array [Parent of i node] >= A[i]

In a max-heap, the root always contains the largest element. In a min-heap, the condition is reversed and the root always contains the smallest element.

Let’s say, we have a heap with elements stored in an array called arr. To convert this array into a heap, access the node in the array. Then, check if its left and right sub-trees are max heaps and if the node itself contains the largest value than all of the child nodes.

Heapsort runs in two phases. In the first phase, we build a heap, and in the second, we translate it into a sorted list by maintaining the max-heap property.

### Implementation of max-heapify is as follows

void maxHeapify(int n, int i) { int large = i, left = 2 * i + 1, right = 2 * i + 2; if (left < n && arr[left] > arr[large]) large = left; if (right < n && arr[right] > arr[large]) large = right; if (large != i) { t = arr[i]; arr[i] = arr[large]; arr[large] = t; maxHeapify(n, large); } }

The logic is simple.

The function takes two parameters: an array, and an index of the node(i) that needs to be heapify.

Initially, we store i in the variable called largest.

If left child ≤ heap‐size and A[left child] > A[i] Then largest ← left child

If right child ≤ heap‐size[A] and a[right child] > A[largest] Then largest ← right child

If largest ≠ i

Then swap A[i] and A[largest]
MAX‐HEAPIFY (A, largest)

Implementing the above logic using C++

void maxHeapify(int n, int i) { int large = i, left = 2 * i + 1, right = 2 * i + 2; if (left < n && arr[left] > arr[large]) large = left; if (right < n && arr[right] > arr[large]) large = right; if (large != i) { t = arr[i]; arr[i] = arr[large]; arr[large] = t; maxHeapify(n, large); } }

Heap sort routine code

void heap_sort() { for (int i = n / 2 - 1; i >= 0; i--) maxHeapify(n, i); for (int i = n - 1; i >= 0; i--) { t = arr[0]; arr[0] = arr[i]; arr[i] = t; maxHeapify(i, 0); } }

Now the above from the main method:

#include <iostream> #include<conio.h> #include<stdlib.h> using namespace std; void heap_sort(); void maxHeapify(int, int); int t, a; int n =5; int arr[5] = {3,4,1,7,5}; int main() { cout << "UnSorted Data :"; for (int i = 0; i < n; i++) { cout << "\t" << arr[i]; } heap_sort(); cout <<endl<< "Sorted Data :"; for (int i = 0; i < n; i++) { cout << "\t" << arr[i]; } cout<<endl; return 0; }

## Comments