The Heap Sort is an in-place, logarithmic sorting algorithm that uses the features of heap data structure.

Suppose an array A with N elements is given. The heap-sort algorithm to sort A consists of the two following phases: Phase 1: Build a heap H out of the elements of A.

Phase

2: Repeatedly delete the root element of H.

For example consider the following array of 6 elements: 15 19 10 7 17 16

0 1 2 3 4 5->array index

After building a heap from these elements, the array will look like this: 19 17 16 7 15 10

0 1 2 3 4 5->array index

Now, delete the root and place it at the last position of the array. Heapify the remaining array: 17 15 16 7 10 19

0 1 2 3 4 5->array index

Now we have a heap of 5 elements. Repeat this process until the heap is empty.

use c++ language