(对d叉堆的分析)d叉堆与二叉堆很类似,但(一个可能的例外是)其中的每个非叶节点有d个孩子,而不是仅仅2个。
a.如何在一个数组中表示一个d叉堆?
b.包含n个元素的d叉堆的高度是多少?请用n和d表示。
c.请给出EXTRACT-MAX在d叉堆最大堆上的一个有效实现,并用d和n表示出它的时间复杂度。
d.给出INSERT在d叉堆最大堆上的一个有效实现,并用d和n表示出它的时间复杂度。
e.给出INCREASE-KEY(A,i,k)的一个有效实现。当k<A[i]时,它会触发一个错误,否则执行A[i]=k,并更新相应的d叉最大堆。请用d和n表示出它的时间复杂度。