Question

Question 1 (CLO-4, PLo-3) Figure 1 show an input tree T. 1. Analyze the tree and mention weather the tree is a heap or not by checking heap's property. If yes, justify your answer. If no, make it a heap by adjusting the node's location 2. Alter the value of T[l1] to 100 using alter-heap algorithm. Analyze the tree again and state whether i. The tree is still a heap or not? ii. If not, which one of the following algorithms you will select to make it a heap? . Percolation Sift-down ii. Use the selected algorithm to maintain the heap 3. Once maintained, outline the maximum value from the heap made in part (ii). 4. Delete the largest element from the heap maintained in part (ii) and remake the heap again by selecting the appropriate algorithm. Insert a new node in the heap mentioned in Figure I. Assign a value to the new node 5. 79. Maintain the max heap structure again by selecting the appropriate algorithm. Question 2 (CLO-4, PLO0-3) 1. Sort the heap mentioned in Figure 1 in ascending order by selecting Min. heap sort algorithm. Show first six iterations only to elaborate your answer. 84 72 70 62 61 19 42 31 50 21 Figure. 1: Input Tree (T)

need full solution of this question plz help me

Answer 1

Answer 1:

Answer 1. Yes, Given tree is heap.

Justification:

As we know that

the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.

the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.

As we can easily observe given tree, it follows the property of max-heap.

Answer 2.

After altering the value of T[11] to 100,

(i) Tree is not a Heap now, because it violates the property of max heap, as 55 < 100.

(ii) I will select Percolation algorithm to make it a heap.

(iii) Percolation algorithm: The heap property is repaired by comparing the added element with its parent and moving the added element up a level (swapping positions with the parent). This process is called "percolation up". The comparison is repeated until the parent is larger than or equal to the percolating element.

For the heap, please refer the following figure:

04 84 Aftes 2 benc olaten 61 31) (5D

Answer 3.

From the heap made in part (ii), the maximum value will be 100 that is root element.

Answer 4.

CAI 84 19 41 81 6l
Answer 5.

Insert a une l . 6 4 70 19 tin (62) 31) (SD

Answer 2:

e aivem Мад 21 lo 21 31 31 4 2 at 3) 31 !스

As we can sort all elements one by one as i did in above figure. I have sort two elements, you can continue like this. At last step we would get sorted array in ascending order.

Please give thumbsup, if you like it. Thanks.