. A d-ary heap, d > 2 is like a heap, but instead of 2 children, nodes may have up to d children. A d-ary heap can be viewed as a complete dary tree (just as the binary heap could be viewed as a complete binary tree). The definition of a complete or full d-ary tree, d > 2, is the same as that of a complete or full binary tree, but where each internal node (except for possibly some nodes in the second lowest level of the tree) has exactly d children instead of only two. In order to answer the questions below, you may need to first describe the functions Parent(i) and Child(i, j), 1 j d, which return, respectively, the parent of node i and the j-th child of node i in the d-ary heap. Assume that the children of a node are ordered from left to right in the d-ary tree representing the d-ary heap. Please briefly justify each of your answers.

(a) How would you represent a d-ary heap using an array ?

(b) Describe the procedures Extract-Max and Insert on a d-ary heap. Your procedures should each run in (logd n) time. Hint: What is the height of a full d-ary tree on n nodes (which will roughly be the same as the height of a complete d-ary tree on n nodes, as in the case of binary trees)?

(c) For a d-ary heap A, an index i, and a key k, describe a procedure Heap-Increase-Key(A, i, k) which sets A[i] = max(A[i], k) and updates the heap structure appropriately that runs in (logd n) time.

(d) How do you compare (in terms of efficiency) two procedures that have running times of (logd n) and (log n) (where d is a constant and log n = log2 n) respectively ?