1 Writing the C code to find the heapsort for an array with

1. Writing the C++ code to find the heapsort for an array with size 26.

2. As for the array (26, 25, 24, …., 1), using your code to find

a) All 26 max-heaps toward heapsort.

b) The heapsort result for (26,25, 24, …, 1)

c) Above a) and b) for any random array with size 26.

Solution

#include <iostream>

using namespace std;
void max_heapify(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;
if (temp > a[j])
break;
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--){
temp = a[i];
a[i] = a[1];
a[1] = temp;
max_heapify(a, 1, i - 1);
}
}
void build_maxheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i--){
max_heapify(a, i, n);
}
}
int main(){
int n=26, i, x;
  
int a[26] = {26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
  
build_maxheap(a,n);
heapsort(a, n);
cout<<\"sorted output\ \";
for (i = 1; i <= n; i++){
cout<<a[i]<<endl;
}
  
}

Sorted output:

1

2

3

4

5

6

7

8

9

10

11

12

13