1. In this problem, we will investigate d-ary max-heaps: A d-ary heap is one in which each node has at most d children, whereas, in a binary heap, each node has at most 2 children.

(a) Describe how to store/represent a d-ary heap in an array.

(b) What is the height of a d-ary heap in terms of d and n?

(c) Re-write function Parent(i) for d-ary heaps, and give a new function Child(i,j) that gives the j-th child of node i (where 1 j d).

(d) Describe, and give pseudocode for, the algorithm Max-Heapify(A,i) for d-ary heaps and give a tight analysis for the worst-case running time of your algorithm.

(e) Describe (semi-formally) how to implement Max-Heapify(A,i) in O((logd n) lg d) time. (Hint: you need auxiliary data structures; the heap itself is not sufficient.)