And have a study guide with solutions but am confused about how they got the ans
ID: 3853166 • Letter: A
Question
And have a study guide with solutions but am confused about how they got the answer for 2A and 2B could someone please explain 2. (20 points) Suppose you have a min-heap with exactly 4 nodes, containing items with priorities 3, 9, 11, and 15 (a) Show every possible min-heap that could match this description. For each, draw the appropriate tree and the array representation Solution: (a) Three posibilities 131 11191 15 I 9 11 11 9 15 11319 1 15 111 9 15 (b) For one of your answers to part (a), show what happens with 4 deleteMin operations. Clearly indicate which heap you are starting with and show the heap after each deleteMin. You can just draw the tree (not the array) after each step. Solution: Cempty treex 11-"> 15 11 15 15 15 Cempty tree> OR 119…> 11 15 ty tree> OR 9 15 11 15…> 15 …>Explanation / Answer
First let me give you over view of min-heap and what is does. A binary heap is like a binary tree which has following properties.
1.It is complete tree.It means all level are completely fillede except the last level if not possible.
2. A binary heap can be min-heap or max-heap. Root should be minimum
So now proceed to part a)
we have elements 3 , 9 , 11, 15.
So lets just start randomly by picking up 3, now 3 is our root element. Now moving to next element 9 we can keep anywhere left or right, 3 is less than 9, remember parent should be less than child so 3 is less than 9 so it is good or else we have shuffle between parent and child. Now moving with 11 and 3, 3 is less than 11 so it also good.
now tree has formed with possible solution 3 as root having child 9 and 11. Now add 15 on left hand side it's parent can be 9 and 11 and both are less than 15 so no need swap between them. So its gives three possible solution as given in the snapshot.
Now moving with part b).
We have three solution
beginning with 3 -9 - 11 -15 as first, here we delete 3 as root and between 9-11-15 , 9 is lowest one it becomes root, after deleteing 9, 11 is becomes root adn lastly 15 is deleted.
Now with 3-11-9-15, delete 3, 9 being lowest becomes root, delete 9, 11 being lowest becomes root and lastly 15 is deleted.
Now with 3-9-15-11, delete 3, 9 being lowest in 9 and 15, 9 becomes root, delete 9 then in 11 and 15, 11 become root and lastly delete 15.
So this is how min-heap happens. let me know if you understood this.