1. 2.

(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 contairn all the values inserted. insert 5 into a . deleteMin of a (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. ii. 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)