Write C language based code to take an array (A) of unsorted positive integers (00 to 99) as input and construct an array B which is equivalent to Max-Heapified Left-justified, Balanced Binary Tree.
".C" file is available in downloadable format at :
(Open the link and click on the download arrow on the top right to download the file.)
Given below is the code for "C program for conversion of Array to Binary Heap" :
-----------------------------------------------------------------------------------
#include <stdlib.h>
#define MAX 20
void maxheapify(int* , int, int);
int* buildmaxheap(int*, int);
void main()
{
int i, t, n;
int *a = malloc(MAX*sizeof(int)); //or int a[MAX];
int *m = malloc(MAX*sizeof(int)); //or int m[MAX];
printf("Enter no of elements in the array\n");
scanf("%d", &n);
printf("Enter the array\n");
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
m = buildmaxheap(a, n);
printf("The heap is\n");
for (t = 0; t < n; t++) {
printf("%d\n", m[t]);
}
}
int* buildmaxheap(int a[], int n)
{
int heapsize = n;
int j;
for (j = n/2; j >= 0; j--)
{
maxheapify(a, j, heapsize);
}
return a;
}
void maxheapify(int a[], int i, int heapsize)
{
int temp, largest, left, right, k;
left = (2*i+1);
right = ((2*i)+2);
if (left >= heapsize)
return;
else {
if (a[left] > a[i])
largest = left;
else
largest = i;
if (right < (heapsize) && a[right] > a[largest])
largest = right;
if (largest!= i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
maxheapify(a, largest, heapsize);
}
}
}
Helpful, but can you tell me why didn't we used static array here? I mean why dynamic array is used?
ReplyDeleteHello. We used dynamic array here, so that we can allocate the memory dynamically, as the amount of cells that we might be asking for may not be available at a single space (as a single block). That's why we are assigning the memory dynamically.
Delete