Question

1. Heaps:

1. Show by hand the Insertion of the following into a Max Binary Heap (aka, a Max Heap): 150, 166, 75, 20, 175, 111, 80, 95, 90, 25, 50, 92, 200, 5, 6. Show any steps that involve swapping nodes.
   

Theory here

2. Show the heap you generated in (a) in array form.
   
   

Array here

3. How could you use a heap to help you efficiently merge many (n> 2) sorted arrays into one sorted array?
   
   

Theory here

Answer 1

Solution:-

Max heap construction with possible swapping is done and can be seen below.

1050) 150 150 166 166 166 75 (166 75 150 TS 150 20 166 166 (175 735 (150 크 150) 175. 16 (150 20 15 1/1 80) 20 175 20 175 175 175 175 166 150 ㅋ IA (ISO ㅋ 166 150) 195 IS 45 80 15 75 20 20 (20) [90) (25) (50 120 90 145

(175. 175. 773 IEE 150 (166 (20) 166 ㅋ 150 (43) 15 75 75 15 0 AD 12.00 CO 95 5 No (20) 250 (3) (25 5) (32) (it) Re (ia) (25) 150)(32) () 20 200) 90 25 92 50 200 166) 175 1 (95 75 750 80 급 90 (25) 500 2 5. 6

Max heap in array form:-

200

166

175

95

75

150

80

20

90

25

50

92

111

5

6

A heap can be used to efficiently merge sorted arrays into one sorted array. The methodology involves the usage of a min heap from which smaller elements are discarded till all the elements of arrays are inserted and you get the desired array. If there are m elements to be inserted in the min heap so the height of the heap would be logm , n*m will be the number of elements in total through all the arrays. Therefore the time taken would be O(n*m*logm).