Please, I need Help with this qustion: This problem is about the array implement

Question

Please, I need Help with this qustion:

This problem is about the array implementation of binary max-heaps. An array implemen- tation of a binary tree (any kind) works like as follows. In class I indexed the array that will contain the binary tree by starting at 1. In this problem I will assume that array indices start at 0. The root of the binary tree is stored in cell 0. In general, if a given vertex v of the tree is stored in cell k, then the left child of v is stored in cell 2k + 1 and the right child is stored in cell 2k + 2. For example, suppose we have a binary tree whose indices contain the five keys 2, 3, 7, 17, 19 like this:

Then an array implementation of this tree with 7 ((a sufficiently large power of 2) - 1) or more cells would be

filled in like this:

To use a binary tree as a binary heap we must, by definition, fill in each level of the tree from left to right. So the tree above should have the shape below in order to be eligible to be a heap:

The corresponding array is

The requirement to fill in each level of the tree from left to right assures there will be no gaps in the array that implements the tree.

Max heaps have an additional requirement: The key in each node must be greater than the key in each child of the node. So, suppose we want to insert a ode with key 100. Since the tree must filled in on each level from left to right, we must insert 100 as shown in the following array:

But 100 is now a child of 7, which violates the Max heap property. To restore the max heap property we ?bubble-up? the node toward the root until the max heap property is restored by repeated swaps of the node with key 100 with its parent.

Suppose we extend this array out to 15 cells:

Show the array after inserting 25, 36, and 1 in that order. During each insertion show the array after each swap individual swap during the bubble-up to restore the max heap property.

Explanation / Answer

//Run this program ... input the numbers u want to see for .. the output would be the final state of array . #include #include 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 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=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=current) { k[parent]=k[child]; parent=child; child=child*2; if(child+1 k[child]) child = child + 1; } k[parent]=current; } /* end of for */ printf(" The sorted array is : "); for(i=1;i

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---