Create a sorting algorithm based on Heap Your sorting algori

Create a sorting algorithm based on Heap. Your sorting algorithm has to be contained in a function: void Heapsort (vector & v) {} The function takes v as a parameter and sorts it by Step 1: sequentially adding elements from v into heap Step 2 extracting elements from the heap back into v Demonstrate the work of your program on a test example. Submission format: screenshots of your program.

Solution

Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end.

step:1

void heapSort(int arr[], int n)

{

    // Build heap (rearrange array)

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(arr, n, i);

    // One by one extract an element from heap for Step2

    for (int i=n-1; i>=0; i--)

    {

        // Move current root to end

        swap(arr[0], arr[i]);

        // call max heapify on the reduced heap

        heapify(arr, i, 0);

    }

}