chapter10

复制本地路径 | 在线编辑
1. Heap
1.1 证明: 当关键码均匀分布时，插入操作时间平均为O(1)
1.2 在上滤过程中，进行赋值改进(若swap执行k次，则3k-->k+1)
1.3 在上滤过程中，进行比较改进(logn-->loglogn)
1.4 举例说明Floyd建队法的过程，并且求出复杂度(上滤)

2. D-Heap
2.1 求出D-Heap的insert,remove操作的时间复杂度
2.2 求出利用D-Heap实现的Prim算法时间复杂度，并说明d取多少最合适

3. Leftist-Heap
3.1 举例说明左式堆的合并操作过程
3.2 证明左式堆的合并时间复杂度为O(logn+logm),即说明高度为O(logn)
3.3 给出左式堆的建堆代码，要求复杂度为O(n)(http://web.onda.com.br/abveiga/capitulo5-ingles.pdf)

4. 对于两个AVL树，高度分别为h和g，保证一棵树的节点大于另一颗的节点，设计合并算法，要求O(max(h,g))

5. 判断题
5.1 对于左式堆来说，左孩子的高度必不小于右孩子，是给证明，否给反例
5.2 对于最小堆中的某个元素，找到其在从小到大的排序中的右节点，复杂度为O(logn)(False,O(n))
chapter10

Comments
