【面试题精选】4 优先级队列，堆积
优先级队列为，首部元素最大，总是删除当前最大元素。并在尾部插入元素。
删除元素的时间复杂度为O(1)，插入元素的时间复杂度为O(lgn)，效率非常高。
C++实现代码如下：
#include <iostream>using namespace std;const int MAX_SIZE = 1024;int Tail = 0;int PriorStack[MAX_SIZE]={0};bool Push(int num);void PrintList();bool inline Exchange(int index1,int index2);bool inline Clear(int index);int Pop();int main(int argc,char * argv[]){Push(6);Push(9);Push(7);PrintList();Pop();PrintList();getchar();return 0;}void PrintList(){for(int i=1;i<=Tail;i++){std::cout<<PriorStack[i]<<"\t";}std::cout<<std::endl ;}/*向优先级队列插入元素，最大的元素在队列首部*/bool Push(int num){if(Tail >= MAX_SIZE){return false;/*溢出*/}Tail ++;PriorStack[Tail] = num;int cur = Tail/2;if(cur < 1){return true;}while(true){/*依次于其父节点比较，如果小于则交换元素*/if(PriorStack[Tail] > PriorStack[cur]){Exchange(Tail,cur);}cur = cur/2;if(cur == 0){break;}}}/*弹出优先级最高的元素，一般为最大值*/int Pop(){if(Tail < 1){return false;}int val = PriorStack[1];Exchange(1,Tail);/*尾部元素与首部元素交换*/Clear(Tail);Tail --;int p = 1;int cur = 2*p;while(true){/*如果父节点元素小于子节点元素则予以交换*/if(PriorStack[p] < PriorStack[cur]){Exchange(p,cur);}p = cur;cur = p *2;if(p >= Tail){break;}}return val;}/*交换两个位置上的元素*/bool inline Exchange(int index1,int index2){int tmp = PriorStack[index2];PriorStack[index2] = PriorStack[index1];PriorStack[index1] =tmp;return true;}/*清空某个位置的元素*/bool inline Clear(int index){PriorStack[index] = 0;return true;}