Problem 5.23. (k-ary heaps) In Section 5.7 we defined heaps in terms of an essentially complete binary tree. It should be clear that the idea can be generalized to essentially complete k-ary trees, for any k > 2. Show that we can map the nodes of a k-ary tree containing n nodes to the elements T[0] to T[n - 1] of an array in such a way that the parent of the node represented in T[i] is found in T[(i -1) k] for i > 0, and the children of the node represented in T[i] are found in T[ik + 1], T[ik + 2],..., T[(i + 1)k]. Note that for binary trees, this is not the mapping we used in Section 5.7; there we used a mapping onto T[1...n], not onto T[O..n -1].

Write procedures sift-down (T, k, i) and percolate (T, k, i) for these generalized heaps. What are the advantages and disadvantages of such generalized heaps?