Part a) Build Heap Write a C program that receives an array with a (size < 100)
ID: 3762222 • Letter: P
Question
Part a) Build Heap 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
Hi,
Below is the solution to your question:
part a):Max Binary heap implementation:
/* C program to build a Max Binary Heap */
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
void maxheap(int *, int, int);
int* buildmaxheap(int *, int);
//Main function
void main()
{
int i, j, n;
//Allocating memory for the nodes
int *a = calloc(MAX, sizeof(int));
int *b = calloc(MAX, sizeof(int));
printf(" Please enter the size of your array: ");
scanf("%d", &n);
printf("Please enter values for your array: ");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
b = buildmaxheap(a, n);
printf("The resulting heap would be: ");
for (j = 0; j< n; j++) {
printf("%d ", b[j]);
}
}
int* buildmaxheap(int a[], int n)
{
int size = n,k;
for (k = n/2; k >= 0; k--) {
maxheap(a, k, size);
}
return a;
}
void maxheap(int a[], int i, int size)
{
int temp, largest_value, left, right;
left = (2*i+1);
right = ((2*i)+2);
if (left >= size)
return;
else {
if (left < (size) && a[left] > a[i])
largest_value = left;
else
largest_value = i;
if (right < (size) && a[right] > a[largest_value])
largest_value= right;
if (largest_value != i) {
temp = a[i];
a[i] = a[largest_value];
a[largest_value] = temp;
maxheapify(a, largest_value, size);
}
}
}
Output:
Please enter the size of your array: 8
Please enter 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
Explaination:
Implementaion:
part b): Implementaion of heap sort algorithm:
BuildMaxHeap
Given an array of n numbers, we can call the buildmaxheap() function n times to create the max heap. Since each call to this function can take upto O(logn) time.
*
* C Program to implement heap sort algorithm
*/
#include <stdio.h>
void main()
{
int heap[10], n, i, j, a, root, temp;
printf(" Enter no of elements to be present in the heap :");
scanf("%d", &n);
printf(" Enter the elements : ");
for (i = 0; i < n; i++)
scanf("%d", &heap[i]);
for (i = 1; i < n; i++)
{
a = i;
do
{
root = (a - 1) / 2;
if (heap[root] < heap[a]) /* to create MAX heap array required */
{
temp = heap[root];
heap[root] = heap[a];
heap[a] = temp;
}
a = root;
} while (a != 0);
}
printf("Heap array now is: ");
for (i = 0; i < n; i++)
printf("%d ", heap[i]);
for (j = no - 1; j >= 0; j--)
{
temp = heap[0];
heap[0] = heap[j] /* Always swap maximum element in the heap with rightmost leaf element */
heap[j] = temp;
root = 0;
do
{
a = 2 * root + 1; /* left most node of root element value in the heap */
if ((heap[a] < heap[a + 1]) && a< j-1)
a++;
if (heap[root]<heap[a] && a<j) /* Again rearrange the max heap array */
{
temp = heap[root];
heap[root] = heap[a];
heap[a] = temp;
}
root = a;
} while (a < j);
}
printf(" The sorted array is : ");
for (i = 0; i < no; i++)
printf(" %d", heap[i]);
}
output:
Enter no of elements to be present in the heap :6
Enter the elements :
6
5
3
1
8
7
2
4
Heap array now is : 6 5 3 1 8 7 2 4
The sorted array is : 1 2 3 4 5 6 7 8
1.Heap sort algorithm starts by building a heap from the given elements,and then heap removes its largest element from the end of partially sorted array.
2.After removing the largest element, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full.
Hope that helps...HAPPY ANSWERING!!!!!!!!!!!!!!!