Problem 1.

Binary Min-Heaps This problem will give you some practice with the basic operations on binary min heaps. You are welcome to show more intermediate trees or arrays than the numbers listed below if you like.

a) Starting with an empty binary min heap, show the result of inserting, in the following order, 12, 10, 4, 8, 6, 7, 15, 3, 14, 9, and 2, one at a time (using percolate up each time), into the heap. Be sure to draw the result after every insertion. By show here we mean draw the resulting binary tree with the values at each node." In addition, give the array representation of your final answer. We expect 11 trees and 1 array as your answer.

b) Instead of inserting the elements in part (a) into the heap one at a time, suppose that you use Floyd's build heap algorithm. Show the resulting binary min heap tree. (It would help if you showed the intermediate trees so if there are any bugs in your solution we will be better able to assign partial credit, but this is not required). In addition, give the array representation of your final answer. We expect 1 tree and 1 array as your answer.

c) Now perform TWO deleteMin operations on the binary min heap you constructed in part (b). Show the binary min heaps that result from these successive deletions (draw the resulting binary tree with values at each node"). Be sure to draw the result after every deletion. In addition, give the array representation of your final answer. We expect 2 trees and 1 array as your answer.