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.

Root of the tree = Array Parent of i node = ⌊i/2⌋ if i ≠ 1
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;
arr = 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 = {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;
}
``` 