优先队列---二叉堆

??????? 使用二叉堆来实现优先队列，可以应用与图的最短路径，最小生成树等算法。优先队列包含一下功能，buildHeap_MIN,效率为O(N), extract_MIN,效率为O(logN), decrease_key,效率为O(logN)等。

#include<iostream>#include<string.h>#include<fstream>using namespace std;class node{public:int key,value;node(){key=-1;value=-1;}};class priority_queue{public:const static int maxm=1005;node array[maxm];int index[maxm];int flag;priority_queue(){this->flag=0;}priority_queue(int flag){this->flag=flag-1;}void heapify_MIN(){int n=flag/2+flag%2-1;for(int i=n;i>=0;i--)buildHeap_MIN(i,flag);}void buildHeap_MIN(int k,int m){int j=2*k+1;if(j>m)return;if(j+1<=m&&array[j].value>array[j+1].value)j=j+1;if(array[k].value>array[j].value){int a=array[k].key;int b=array[j].key;index[a]=j;index[b]=k;node temp=array[k];array[k]=array[j];array[j]=temp;buildHeap_MIN(j,m);}}node extract_MIN(){node res=array[0];int a=array[0].key;int b=array[flag].key;index[a]=flag;index[b]=0;node temp=array[0];array[0]=array[flag];array[flag]=temp;this->flag--;buildHeap_MIN(0,flag);return res;}void decrease_key(int k,int key){if(k==0&&key<array[k].value){array[k].value=key;return;}if(array[k].value<=key)return;else{int n=k/2+k%2-1;if(array[n].value>key){int a=array[k].key;int b=array[n].key;index[a]=n;index[b]=k;node temp=array[k];array[k]=array[n];array[n]=temp;decrease_key(n,key);}else{array[k].value=key;return;}}}};int cases,n,dist;const int maxm=10000;int graphMatrix[1001][1001];int favorate[1001];int s[1001];int path[1001];int main(){/*ifstream txtfile;txtfile.open("e:\\zoj\\zoj_1586.txt");if(!txtfile){cerr<<"open error"<<endl;exit(1);}txtfile>>cases;*/cin>>cases;while(cases--){//txtfile>>n;cin>>n;for(int i=0;i<n;i++){//txtfile>>favorate[i];cin>>favorate[i];}//memset(graphMatrix,0,sizeof(graphMatrix));memset(s,0,sizeof(s));for(int i=0;i<n;i++)for(int j=0;j<n;j++){//txtfile>>dist;cin>>dist;graphMatrix[i][j]=dist+favorate[i]+favorate[j];}priority_queue q(n-1);for(int i=1;i<n;i++){path[i]=0;s[i]=0;}path[0]=0;s[0]=1;for(int i=0;i<n-1;i++){q.array[i].value=graphMatrix[0][i+1];q.array[i].key=i+1;}for(int i=1;i<n;i++){q.index[i]=i-1;}q.heapify_MIN();int result=0;for(int i=1;i<n;i++){node p=q.extract_MIN();s[p.key]=1;result+=p.value;//cout<<p.key<<" ";for(int j=1;j<n;j++){if(s[j]==0&&j!=p.key){int index=q.index[j];if(graphMatrix[p.key][j]<q.array[index].value){q.decrease_key(index,graphMatrix[p.key][j]);path[j]=p.key;}}}}//cout<<endl;cout<<result<<endl;}return 0;}

?