problem 6-2

6-2 Analysis of d-ary heaps
A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
a. How would you represent a d-ary heap in an array?
b. What is the height of a d-ary heap of n elements in terms of n and d?
c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
e. Give an efficient implementation of INCREASE-KEY(A,i,k) which flags an error if k < A[i] , but otherwise sets A[i] = k and then updates the d-ary maxheap structure appropriately. Analyze its running time in terms of d and n.

a. A d-ary can be represented in a single dimensional array with elements A[1]..A[d+1] (for java A[0] to A[d]) and for the root and it children. The children of children can be represented from $A[d+2]..A[d^2+d+1]$(this is for the whole grandchildren level of the root.For java it will be $A[d+1]..A[d^2+d]$). It will easier if you can draw 3 and 4 ary trees to understand.This will continue for its children as well.
The procedure for GET-PARENT and GET-CHILD are as follows:
GET-PARENT
return $\lfloor (i+2)/d+1 \rfloor$ (java: (i-1)/d)
for get child we need to define a new variable j $1 \leq j \leq d$
GET-CHILD
return d(i-1)+j+1 (java: d(i)+j)

b. The height of the tree can be calculated same as exercise 6.1-2. The no of elements can be bounded by max and min no of elements. $$ d^(h) \leq n \leq d^(h+1) -1 $$ $$ d^(h) \leq n \leq d^(h+1) -1 \lt d^(h+1) $$ $$ d^(h) \leq n \lt d^(h+1) $$ Applying logarithm for above equation: $$ log d^(h) \leq log n \lt log d^(h+1) $$ $$ h log d \leq log n \lt (h+1) log d $$ $$ h \leq log n /log d \lt (h+1) $$ since h is an integer it is $\lfloor log_d n \rfloor$
c. EXTRACT-MAX(A,d)
int max = A[1]
A[1] = A[A.heapsize]
MAX-HEAPIFY(A,1,d)
return max; MAX-HEAPIFY(A,i,d)
//first child: d(i-1)+j+1 = d(i-1)+1+1 to last child d(i-1)+d+1 = di+1
largest = i
for j = d(i-1)+2 to d*j (iterate from first child to last)
if(j <= A.heapsize && A[j] > A[i] )
largest = j
if largest != i then
swap A[largest] and A[i]
MAX-HEAPIFY(A,largest,d)
d.
The only change from binary to n-ary is we need to send d(the no of children) to the insert prcoedure. INSERT(A,key,d)
A.heapsize = A.heapsize+1;
A[A.heapsize] = $- \infty $
MAX-HEAP-INCREASE(A,A.heapsize,key,d)
We see the implementation of MAX-HEAP-INCREASE in section e of the solution(which is below). The running time depends on MAX-HEAP-INCREASE above procedure takes constant time except for MAX-HEAP-INCREASE.
e.
MAX-HEAP-INCREASE(A,i,key,d) IF A[i] > key error("Invalid Key") A[i] =key While i > 1 and A[parent(i)] < A[i] Swap A[i] and A[parent(i)] i = parent(i) parent(i) return (i - 1)/d+1 In the worst case an element has to move from leaf node to root which is height of the tree. So the runnning time $\theta(h)$ = $\theta(log_d n)$