问题: d叉堆性质与二叉堆相似,但其每个非叶子结点有d个孩子;
1) 如何在一个数组中表示一个d叉堆?
2) 包含n个元素的d叉堆的高度是多少?
3) 给出 EXTRACT-MAX在d叉堆的有效实现,并用d与n表示其时间复杂度.
4) 给出INSERT在d叉堆的有效实现,并用d与n表示其时间复杂度.
5) 给出INCREASE-KEY(A, i, k)的有效实现。当k < A[i]时,它会触法一个错误,否则执行A[i] = k,
并更新相应的d叉最大堆,使用d与n表示其时间复杂度。
3) HEAP-EXTRACT-MAX算法就很适用于d叉堆;但问题在于MAX-HEAPIFY算法。
在此需要将处理的结点和它所有的孩子进行比较。所以运行的时间应为Θ(dlogn)。
4) MAX-HEAP-INSERT算法也适用于此。最坏情况下的运行时间就是堆的高度即Θ(logn)。
5) HEAP-INCREASE-KEY算法适用,运行时间为O(logn)