算法导论 6-2 d叉堆
浏览数：32 /
时间：2015年06月08日
问题: 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算法。
在此需要将处理的结点和它所有的孩子进行比较。所以运行的时间应为Θ(dlogdn)。
4) MAX-HEAP-INSERT算法也适用于此。最坏情况下的运行时间就是堆的高度即Θ(logdn)。
5) HEAP-INCREASE-KEY算法适用，运行时间为O(logdn)
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
