Question

in C++

HeapSort Implement the heapsort algorithm for sorting an array of integers. Input structure Each case starts with an integer number which indicates the number of elements to be sorted. Then, the elements follow, one per line. You can assume the input is correctly structured (i.e., no data are missing Output structure Output the sorted sequence separeted by";" (in non-decreasing order). Do not insert spaces or a new line at the beginning or at the end of any element.

Answer 1

#include <iostream>

using namespace std;

// A function to heapify the array.

void MaxHeapify(int a[], int i, int n)

{

int j, temp;

temp = a[i];

j = 2*i;

while (j <= n)

{

if (j < n && a[j+1] > a[j])

j = j+1;

// Breaks if the value of parent is already greater than value of child.

if (temp > a[j])

break;

// Switching value with the parent node if temp < a[j].

else if (temp <= a[j])

{

a[j/2] = a[j];

j = 2*j;

}

}

a[j/2] = temp;

return;

}

void HeapSort(int a[], int n)

{

int i, temp;

for (i = n; i >= 2; i--)

{

// Storing maximum value at the end.

temp = a[i];

a[i] = a[1];

a[1] = temp;

// Building max heap of remaining element.

MaxHeapify(a, 1, i - 1);

}

}

void Build_MaxHeap(int a[], int n)

{

int i;

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

MaxHeapify(a, i, n);

}

int main()

{

int n, i;

//"Enter the number of data element to be sorted: ";

cin>>n;

n++;

int arr[n];

for(i = 1; i < n; i++)

{

cin>>arr[i]; // Enter the elements to be sorted

}

// Building max heap.

Build_MaxHeap(arr, n-1);

HeapSort(arr, n-1);

// Printing the sorted data.

for (i = 1; i < n; i++)

cout<<arr[i]<<";"; //prints the sorted form

return 0;

}

for any quarries please comment.

thank you.