COMP 3804/Math 3804: Assignment 2

Question 1 [15 marks]

Consider a 4 _ heap to be a heap-ordered tree in which each internal node has 4 children, all leaves are on at most two adjacent levels, and, on the last level, all leaves are as much to the left as possible.  Let n be the total number of nodes in the tree and assume that n = 4 * k + 1, for some positive integer k .

1.  State precisely:

. how many leaf-nodes a 4 _ heap on n nodes can have minimally and maximally, . how many nodes there are on each level, i, (excluding the lowest level),               .  an expression, phrased in terms of n, for the height of the tree,

. how many nodes there are on all levels together (excluding the lowest level),      .  a relation between the total number of internal nodes and the number of leaves.

2. Assume the tree is stored in an array H[1 ...  n].  (Note: we start with index 1 not 0.)  Give address formulae for: the children of an internal node stored at H[i] and the parent node of a node stored at H[i].

Question 2 [11 marks]

1. For standard binary heaps, we also store the heap in an array H[1....n].   Now, state par- ent/child index relations, but use the bit representation of the array indices. So, state (child to parent) and (parent to child) array index relations using the binary representation of in- dices.  So, we get e.g., the children of the root are stored at binary(10) and binary(11) and the parent of binary(10) and binary(11) is the root stored at binary(1).

2. Let the ithparent(node) be recursively defined as follows: for i = 0 the ithparent(node) is the node itself.

for i > 1, ithparent(node) is the parent of (i _ 1)stparent(node).

Now, state a simple formula (in binary) for the ith parent of a node stored at binary(b1 ...bm).