C) Compare between the running time in the BEST CASE between insertion sort, merge sort and heap sort in term of Big-O.

Algorithm	insertion sort	merge sort	heap sort
Time complexity in best case

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Q3)

Draw the resulted heap tree for the following array A after calling Build-MAX-Heap, and show your work over the tree you build.

30	15	25	8	4	9	1	16	90

Array after applying the build-max heap function:

Apply heap sort to the resulting heap from previous question.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Q4)

A) Apply EXTRACT-MAX(A, 10)on the following heap A, and show all steps to build the new heap tree.

10

9

3

20

8

50

30

1

0

15

B) Apply INCREASE-KEY(A, 9, 44) on the following heap A, and show all steps to build the new heap tree.

12

9

5

25

8

40

30

11

10

20