PLEASE DO NOT COPY OTHER ANSWERS

(c) A balanced binary heap is to be constructed using the following data elements: 95 56 34 86 41 17 29 32 58 3 4 11 60 77 82 using a bottom up heap construction method. (i) Explain how the bottom up construction method can be shown to have running time complexity O(n) where n is the number of elements in the binary heap. You may find it helpful to recall that: h=0 h 2 Ian h=0 1.e. that that s + + + + + - 2 as h00 [10 marks] 5 (ii) Show the heap that results from the bottom up construction. Fill the heap levels starting from the lowest first, and working from the right hand side to the left hand side. [5 marks]