/*************************堆构造优先级队列*******************/ class PriorityQueue:public HeapSort { public: //取出最大值并重新构造为最大堆 int HeapExtractMax(int *A,int len); //将元素i的值增加到key,且key不能小于i原来的值 void HeapIncreaseKey(int *A,int i, int key); //插入一个新的元素 void HeapInsert(int *A,int key,int maxIndex); }; //len实际数组的最大下标 int PriorityQueue::HeapExtractMax(int *A,int len) { if(len < 1)//长度小于1,异常 throw exception("heap underflow"); int max = A[1]; A[1] = A[len]; len -= 1;//长度减1 Max_Heap(A,1,len);//重新构造最大堆 return max; } void PriorityQueue::HeapIncreaseKey(int *A,int i, int key) { if(key < A[i]) return; A[i] = key; //新增加的key值可能比父大,因此需要在父以上的节点进行判断和交换 while ((i >1)&&(A[i>>1] < A[i])) { SwapData(A,i,i>>1); i = i>>1; } } //注意:maxIndex插入之前的最大下标 void PriorityQueue::HeapInsert(int *A,int key,int maxIndex) { maxIndex += 1; A[maxIndex] = INT_MIN;// HeapIncreaseKey(A,maxIndex,key); } //AA最后一个数是给HeapInsert用的 //其余操作不用最后一个0 int AA[]= {0,27,17,3,16,13,10,1,5,7,12,4,8,9,0,0}; int lenAA = sizeof(AA)/sizeof(int); int _tmain(int argc, _TCHAR* argv[]) { PriorityQueue hs; hs.Build_Heap(AA,lenAA-1); //hs.HeapExtractMax(AA,lenAA-1); //hs.HeapIncreaseKey(AA,4,80); hs.HeapInsert(AA,2,lenAA-2); hs.OutToScreen(&AA[0],lenAA); return 0; } 伪码