算法导论第六章6.5优先队列课后答案。

6.5-1 试说明HEAP-EXTRACT-MAX在堆A={15,13,9,5,12,8,7,4,0,6,2,1}上的操作过程。

[cpp] view plaincopy

1. <span style="font-size:14px;">HEAP-EXTRACT-MAX(A)  
2. if(A.heap-size<1)        //堆中元素是否为空  
3.   error"heap underflow"  //如果是空的，那么返回错误  
4. max=A[1]                 //将最大堆最大元素也就是第一个元素保存起来  
5. A[1]=A[A.heap_size]      //将堆中最后一个元素赋值给第一个元素  
6. A.heap_size=A.heap_size-1//堆元素数量减少1  
7. MAX-HEAPIFY(A,1)//保持最大堆的性质  
8. return max//返回这个最大元素  

6.5-2/6.5-4试说明MAX-HEAP-INSERT(A,10)在堆A={15,13,9,5,12,8,7,4,0,6,2,1}上的操作过程。

[cpp] view plaincopy

1. <span style="font-size:14px;">MAX-HEAP-INSERT(A,key)  
2. A.heap-size=A.heap-size+1          //将堆中元素个数+1  
3. A[A.heap-size]=负无穷大            //因为堆中新的最后一个元素开始没有被赋值，所以是一个不确定的数，而  
4. //这个不确定的数可能大于待插入的key，这样就不符合原书本意。而被赋值为负无穷大后，保证了key>A[A.heap-size]  
5. HEAP-INCREASE-KEY(A,A.heap-size,key)//在key>A[A.heap-size]前提条件满足的情况下，增加A[A.heap-size]值到key实现插入  

6.5-3 要求用最小堆实现最小优先队列，请写出HEAP-MINMUM,HEAP-EXTRACT-MIN,HEAP-DECREASE-KEY和MIN-HEAP-INSERT的伪代码。

这里已经给出最小堆实现最小优先队列的代码。http://blog.csdn.net/z84616995z/article/details/17797393

6.5-5试分析在使用下列循环不变量时，HEAP-INCREASE-KEY的正确性：
     在算法的第4-6行while循环每次迭代开始的时候，子数组A[1..A.heap-size]要满足最大堆的性质。如果有违背，那么只有一种可能，A[i]>A[PARENT(i)].这里，你可以假定在调用HEAP-INCREASE-KEY时，A[1..A.heap-size]是满足最大堆性质的。


初始：在循环开始前，除了刚增加的A[i]=key不满足最大堆性质，其他元素都满足最大堆性质。
保持：在循环过程中，通过不断交换key值与其parent值，并且不断更新parent值来使增加元素值得堆满足最大堆性质。
终止：当i=1或A[PARENT(i)]>=A[i]时，代表所有元素已经排好，并且满足最大堆，那么循环自然终止。


6.5-6 在HEAP-INCREASE-KEY的第5行的交换操作中，一半需要通过三次赋值来完成。想一想如何利用INSERTION-SORT内循环部分的思想，只用一次赋值就完成一次交换操作？

[cpp] view plaincopy

1. <span style="font-size:14px;">void HEAP_INCREASE_KEY(int A[],int i,int key)  
2. {  
3.     if (key<A[i])  
4.     {  
5.         return ;  
6.     }  
7.     A[i]=key;  
8.     while (i>0&&A[PARENT(i)]<=key)  
9.     {  
10.         //swap(A[i],A[PARENT(i)]);  
11.         A[i]=A[PARENT(i)];//利用插入排序内部循环思想  
12.         i=PARENT(i);  
13.     }  
14.     A[i]=key;  
15. }  

6.5-8 HEAP-DELETE(A,i)操作能够将结点i从堆A中删除。对于一个包含n个元素的堆，请设计一个能够在O(lgn)时间内完成的HEAP-DELETE操作。

[cpp] view plaincopy

1. <span style="font-size:14px;">HEAP-DELETE(A,i)  
2. HEAP-INCREASE-KEY(A,i,A[1])//将待删除的元素增加到数组最大值也就是最大堆第一个元素的值  
3. HEAP-EXTRACT-MAX(A)//数组中有2个最大值，利用此函数删除一个实现对A[i]的删除。  
4.   

这里是6.5-9具体解答。http://blog.csdn.net/z84616995z/article/details/17883173