2, 5+5+5+5=20 points] (d-ary heaps) A d-ary heap is defined analogously to a binary heap (see Chapter 2.5 of our textbook), except that with at most one exception, internal nodes have d instead of 2 children (a) Consider an array implementation of d-ary heaps. Note that for d > 2 it is most convenient to put the root in position 0 of the array (the index of the root is 0), while for d-2 it is better to put the root at position 1. How can you compute Child(i, k), the index of the k-th child of the node with index i? How can you compute Parent (i), the index of the parent of the node with index i? (b) What is the minimal number of elements of a d-ary heap of height h? Note that the eight of a tree is measured with edges. E.g., a 1-vertex tree has height 0 (c) On Insertion of a new element into a d-ary heap with n nodes, we need to run a procedure Heapify-up as on page 61 of the textbook. Write the procedure for d-ary heaps, and analyze its running time as a function of n and d. O-notation is good enough, but remember that d is not considered to be a constant (d) ExtractMin requires a procedure Heapify-down as on page 63 of the textbook. Analyze the time of Heapify-down for a d-ary heap, again as a function of n and d