Part a) Write a C program that receives an array with a (size < 100) and produce
ID: 3762220 • Letter: P
Question
Part a)
Write a C program that receives an array with a (size < 100) and produces its max binary heap.
The following represents a sample input / output of the desired program:
Please enter the size of your array:
8
Please enter 8 values for your array:
6 5 3 1 8 7 2 4
The resulting heap would be: 8, 6, 7, 4, 5, 3, 2, 1
Part b) Implement Heapsort
Following part a) implement healpsort algorithm where it receives an array and its size and sorts that array. Your code should print the sorted array at the end of the main function.
void heap_sort_algorithm( double *a, int count)
Your heapsort function should not return any value.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct MaxHeap
{
int size;
double* array;
};
void swap(double* a, double* b) { double t = *a; *a = *b; *b = t; }
void maxHeapify(struct MaxHeap* maxHeap, int idx)
{
int largest = idx;
int left = (idx << 1) + 1;
int right = (idx + 1) << 1;
if (left < maxHeap->size &&
maxHeap->array[left] > maxHeap->array[largest])
largest = left;
if (right < maxHeap->size &&
maxHeap->array[right] > maxHeap->array[largest])
largest = right;
if (largest != idx)
{
swap(&maxHeap->array[largest], &maxHeap->array[idx]);
maxHeapify(maxHeap, largest);
}
}
struct MaxHeap* createAndBuildHeap(double *array, int size)
{
int i;
struct MaxHeap* maxHeap =
(struct MaxHeap*) malloc(sizeof(struct MaxHeap));
maxHeap->size = size;
maxHeap->array = array;
for (i = (maxHeap->size - 2) / 2; i >= 0; --i)
maxHeapify(maxHeap, i);
return maxHeap;
}
void heap_sort_algorithm(double *a, int count)
{
struct MaxHeap* maxHeap = createAndBuildHeap(a, count);
while (maxHeap->size > 1)
{
swap(&maxHeap->array[0], &maxHeap->array[maxHeap->size - 1]);
--maxHeap->size;
maxHeapify(maxHeap, 0);
}
}
void printArray(double* arr, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("%.2f ", arr[i]);
}
int main()
{
double *arr;
int size = sizeof(arr)/sizeof(arr[0]);
printf("Please enter the size of your array: ");
scanf("%d", &size);
arr = (double *)malloc(sizeof(double)*size);
printf("Please enter 8 values for your array: ");
for (int i=0; i<size; i++) {
scanf("%lf", &arr[i]);
}
printf("Given array is ");
printArray(arr, size);
printf(" ");
createAndBuildHeap(arr, size);
printf("Max Heap of array: ");
printArray(arr, size);
printf(" ");
heap_sort_algorithm(arr, size);
printf(" Sorted array is ");
printArray(arr, size);
printf(" ");
return 0;
}