Invariants, Proofs and Sequences

(a) Assume you have an array-based binary heap: a. with the contents 1,4,7,8,9,10,14,12,15,13,17,12 Show the contents of a after each of the following two operations Show your working for each operation including the content of the list at its intermediate stages. You can assume a is large enough to contain all the values inserted e insert 5 into a o deleteMin of a [6 marks] (b) The following questions relate to implementations of unbounded ar rays. Read both parts before answering either of them i. Describe an implementation of an unbounded array that has amor- tised cost of O(1) on both pushBack and popBack operations. In your description make sure you say how and when the necessary allocations and deallocation operations are performed. [5 marks] 11. Use amortised analysis to demonstrate that pushBack and popBack can be performed on the structure you described in part (i) above at an amortised cost of O(1) [6 marks]