Show that the construction of a max-heap from an unsorted array using iterations of the algorithm Downward heapify given in the lecture notes takes O(n) operations. For simplicity, you may use n = 2^h ?1 for your analysis. h is 1 when there is only one node in the heap.

Function Downward heapify (arrayll, i, n): temp r ? array [i] ; while ((j- 2*i+1) S n) if (j ? n and array[j] ? array[j+1]) if array [j]) (temp r 2 break else array [i] ? array[j] arrayli]