优先级队列几个应用详解.docxVIP

优先级队列几个应用详解优先级队列区别于普通队列的一点是：优先级队列如果插入的节点是结构体类型，则要在结构体中重载比较操作符函数。示例代码如下：//优先级队列的使用测试//优先级队列跟对列的使用方式的区别是优先级队列在插入元素时//在将元素插入队尾后还要根据比较值对该元素进行位置的调整#includeiostream#includequeueusing namespace std;struct Node{int key;charch;//只有重载操作符函数时，如果将改为为什么不行，出现error C2784的错误friendbool operator (Node node1,Node node2){//为从大到小排列，为从小到大排列return node1.keynode2.key;}friendbool operator (Node node1,Node node2){return node1.keynode2.key;}};int main(){//对于优先队列中包含结构体或者类的类型，该结构体或者类必须包含比较操作符的重载//因为优先级队列在插入时，是按照结构体中的某一个元素进行比较，如果//不重载比较操作符，优先级队列比较的是结构体，而我们知道结构体是无法直接进行比较的。//如下定义优先级队列qu，less表示按照递减的顺序插入元素，换成greater则表示按照递增的//方式插入元素priority_queueint,vectorint,lessintqu;//定义如下的que优先级队列，会默认按照从大到小对插入元素进行排列//所以在没有定义时，会出现错误priority_queueNodeque;priority_queueNode,vectorNode,lessNodeqe;Node node[10];inti;int a[10]={4,2,1,3,6,8,7,9,10,5};char b[10]={a,b,c,d,e,f,g,h,i,j};//从小到大插入元素for(i=0;i10;i++){qu.push(a[i]);}for(i=0;i10;i++){coutqu.top()endl;qu.pop();}coutendl;//默认从大到小插入元素for(i=0;i10;i++){node[i].key=a[i];node[i].ch=b[i];que.push(node[i]);}for(i=0;i10;i++){coutque.top().key que.top().chendl;que.pop();}coutendl;//利用了priority_queueNode,vectorNode,lessNodeqe;这个定义后可以//将元素从大到小插入元素，但是注意的是结构体中必须重载操作符，不然会出错for(i=0;i10;i++){node[i].key=a[i];node[i].ch=b[i];qe.push(node[i]);}for(i=0;i10;i++){coutqe.top().key qe.top().chendl;qe.pop();}return 0;}疑问解答：在编写代码的时候，在只有一个重载操作符函数时，我们将改为，que.push(node)，出错，错误代号是：C2784.后来发现原因是：我们如下定义的que, priority_queueNodeque;而默认的que插入是从大到小，所以在结构体中要重载,如果我们将其修gai为则que的push函数找不到相应的操作符，就会出错。另外，如果我们想向优先级队列中插入指针元素时该怎么办？是不是将priority_queueNodeque;改为priority_queueNode*que;就ok了?不是！因为我们不能用结构体中重载的操作符对que中的元素进行比较，结构体中重载的操作符是类Node的操作符，而que中的是指针类型的Node节点，它与结构体中重载的操作符无法匹配。所以我们要另想办法。那我们将friend bool operator (Node node1,Node node2)修改为friend bool operator (Node* node1,Node* node2)，也就是传递的是Node的指针行不行呢? 答案是不可以，因为根据c++primer中重载操作符中讲的“程序员只能为类类型或枚举类型的操作数定义重载操作符，在吧操作符声明为类的成员是，至少有一个类或枚举类型的参数按照值或者引用的方式传递”，也就是说friend bool operator (Node* node1,Node* node2)形参中都是指针类型的是不可以的。我们可以如下解决此问题。//在优先级队列中存入指针类型的节点#includeiostream#in