Implement the following algorithm, which is given a duplicate-free array array as input, in C++. whatDoIDo (array):

Problem 3 (4+2+2 marks). (a) Implement the following algorithm, which is given a duplicate-free array array as input, in C++. whatDoIDo (array): 1) Build a heap from array (using buildHeap as explained in class). where the heap starts at position array [0] 2) Starting from j = size of array - 1, as long as j>0: i. Swap the entries array [O] and array [j] . ii. Percolate down array (0), but only within the subarray array [O..j-1). iii. Decrement j by 1. Provide three input /output examples for duplicate-free arrays of size about 10. (b) What does whatDo ID do? Explain your answer (c) What is the worst-case running time of whatDo ID0, in dependence of the size N of the given array? Explain your