6-2（对d叉堆的分析）d叉堆与二叉堆很类似，但（一个可能的例外是）其中的每个非叶节点有d个孩子，而不是仅仅2个。
a. 如何在一个数组中表示一个d叉堆？
假设数组从$A[1]$开始,它作为根，那么$A[1]$有d个孩子分别是$A[2]…A[d+1]$，共d个。那么对于$A[2]…A[d+1]$共d个结点，一共有$d^2$个结点，从$A[d+2]….A[d^2+d+1]$。依次类推。那么对于一个编号为$i$的结点的第$j$个孩子$(1 \leq j \leq d)$，
D-ARY-Parent(i)
return $\lfloor (i-2)/d+1 \rfloor$
D-ARY-Child(i,j)
return $\lfloor d(i-1)+j+1$
i的d个结点从$d(i-1)+2到di+1$。
结合画图，不难推出。
自己可以通过 D-ARY-Parent(D-ARY-Child(i,j))=i 来验证一下。二叉堆是当$d=2$时的一个特例。
b. 包含n个元素的d叉堆的高度是多少?请用n和d表示。
类似二叉堆的推导过程。不难的得出一个n个元素的d叉堆，有$\Theta(log_dn)=\Theta(lgn/lgd)$。
c. 请给出EXTRACT-MAX在d叉堆上的一个有效实现，并用d和n表示出它的时间复杂度。
对于d叉堆的EXTRACT-MAX实现，与树中二叉堆的实现相同，只需要修改MAX-HEAPIFY在下放的过程中，是与d个孩子比较，而不是2个孩子。对于每一层的下放，最差情况下比较d次。那么对于一个n个结点的d叉堆来说。EXTRACT-MAX的时间复杂度为 $\Theta(dlog_dn)=\Theta(dlgn/lgd)$。
d. 给出INSERT在d叉最大堆上的一个有效实现，并用d和n表示它的时间复杂度。
树中给出的二叉堆的MAX-HEAP-INSERT的实现同样适用与d叉堆。该过程只需要访问结点的parent结点，其他并没有改变。最坏情况下时间复杂度为$\Theta(h)$。h为d叉堆的高度，前面已求出，$h=\Theta(lgn/lgd)$。
e. 给出INCREASE-KEY(A,i,k)的一个有效实现，当$k<A[i]$时，它会触发一个错误，否则执行$A[i]=k$,并更新相应的d叉最大堆。请用d和n表示出它的时间复杂度。
跟书本的实现一致。只需要将计算parent的结点的公式替换即可。最坏情况下的时间复杂度为$\Theta(h)=\Theta(log_dn)=\Theta(lgn/lgd)$。