MinHeapify/InsertInHeap

QUESTION: Answer the following questions briefly (in NO MORE THAN 3 LINES) and to the point. There is no partial credit for any of these. You have to get your answers exactly right.

(a)    Following is an array to be converted into a binary Min-Heap, using repeated MinHeapify/InsertInHeap calls. Show the contents of this array after the Min-Heap has been constructed.    

0	1	2	3	4	5	6	7	8	9	10	…
-	7	14	10	15	5	13	4	21	2	11	…

SOLUTION

2 4 5 7 11 13 10 21 15 14     (values start at index 1)

(b)   Consider the following heap of letters in array format:

0	1	2	3	4	5	6	7	8	9	10	11	12	13
-	Z	W	Y	T	G	K	V	R	S	F	A	-	-

Delete the maximum key. Give the resulting binary heap in array format. Circle those values that changed positions.                     

SOLUTION

Y W V T G K A R S F       (values start at index 1 and values that change are Y, V and A)