d-Heap Arithmetic

Binary heaps implemented using an array have the nice property of finding children and parents of a node using only multiplication and division by 2 and incrementing by 1. This arithmetic is often very fast on most computers, especially the multiplication and division by 2 since these correspond to simple bitshift operations. In d-heaps, the arithmetic is also fairly straightforward, but is no longer necessarily as fast. In this problem you will figure out how the arithmetic works in those heaps.

a) We will begin with considering a 3-heap (a heap where each node has <= 3 children. If a 3-heap is stored as an array, for an entry located at index i, what are the indices of its parent and its children? You may find it convenient to place the root at index 0 instead of 1 to simplify calculations (be sure to specify if you make this change). Hint: the solution should be very concise. If it is becoming complicated, you might want to rethink your approach.

b) Generalize your solution from (a) to work for d-heaps in general. If a d-heap is stored as an array, for an entry located at index i, what are the indices of its parent and its children?

c) For what values of d will these operations be implementable with bit shifts instead of divisions and multiplications?

d) If a d-heap has height h, what is the maximum number of nodes that it can contain? What is the minimum? (again, give an exact expression, NOT something in big-O or theta etc.) SHOW how you came up with your answer.

e) If a d-heap has n nodes, what will its height be? (give an exact expression, not something in big O or theta etc.) SHOW how you came up with your answer.