please write the algorithm for the following propblem and explain your answer. I
ID: 3677080 • Letter: P
Question
please write the algorithm for the following propblem and explain your answer.
In Section 5.7 we defined heaps in terms of an essentially complete binary tree. It should be clear that the idea can be generalized to essentially complete k-ary trees, for any k 2. Show that we can map the nodes of a k-ary tree containing n nodes to the elements T[0] to T[n - 1] of an array in such a way that the parent of the node represented in T[i] is found in T[ (i - 1) k) for i > 0, and the children of the node represented in T[i] are found in T[ik + 1], T[ik + 2],..., T[(i + 1)k). Note that for binary trees, this is not the mapping we used in Section 5.7; there we used a mapping onto T[1.. n], not onto T(0.. n - 1). Write procedures sift-down (T,k,i) and percolate (T, k, i) for these generalized heaps. What are the advantages and disadvantages of such generalized heaps? For an application where they may be useful, see Problem 6.16.Explanation / Answer
/* HPSORT.C : PROGRAM TO CREATE A HEAP AND TO SORT A HEAP, HEAP IS STORED IN AN ARRAY */
#include<stdio.h>
#include<conio.h>
void crheap(int [], int);
void processheap(int [],int);
int main(void)
{
int k[50],child,parent,q,key,n,t,i;
clrscr();
printf(" enter the no. of elements: ");
scanf(" %d",&n);
printf(" Now enter the array elements: ");
for(i=1;i<=n;i++)
scanf(" %d",&k[i]);
crheap(k,n);
processheap(k,n);
return(0);
}
/*function to create a heap, in this algorithm the value of a child
node is saved into a key and then if its parent has value less than the
key then the parent node is shifted to its child place and this process
of copying the parent node to its child's place continues until the
correct place of key is found or the root is reached, in that case key
is inserted at the root's place
function to create a heap, in this algorithm every time
a child node has value greater than its parent the two are interchanged */
void crheap(int k[],int n)
{
int i,q, parent,child,temp;
for(q=2;q<=n;q++)
{
child=q;
parent=(int)child/2;
while(child >1 && k[child] > k[parent])
{
temp=k[child];
k[child]= k[parent];
k[parent]=temp;
child=parent;
parent=(int)child/2;
if(parent < 1)
parent=1;
}
}
printf(" Now the array in heap form is: ");
for(i=1;i<=n;i++)
printf(" %3d",k[i]);
}
/* function to sort a heap */
void processheap(int k[],int n)
{
int current,parent,child,i,maxnodes;
for(maxnodes=n;maxnodes>=2;maxnodes--)
{
current=k[maxnodes];;
k[maxnodes]=k[1];
/* adjust the array to be a heap of size n-1 */
parent=1;
/* obtain the larger of the root's children */
if (maxnodes-1 >= 3 && k[3] > k[2])
child=3;
else
child = 2;
/* move keys upwards to find place for current */
while (child<=maxnodes-1 && k[child]>=current)
{
k[parent]=k[child];
parent=child;
child=child*2;
if(child+1 <= maxnodes-1 && k[child+1] > k[child])
child = child + 1;
}
k[parent]=current;
} /* end of for */
printf(" The sorted array is : ");
for(i=1;i<=n;i++)
printf("%4d",k[i]);
getch();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.