首页 > 代码库 > 经典白话算法之优先级队列

经典白话算法之优先级队列

2024-07-02 16:16:02   225人阅读

<1>概念

优先级队列，顾名思义，就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体，不仅可以存储数据，还可以将这些数据按照我们设定的规则进行排序。优先级队列是堆的一种常见应用。有最大优先级队列（最大堆）和最小优先级队列（最小堆）。优先级队列是一种维护有一组元素构成的集合S的数据结构。

<2>优先队列支持的基本运算

[cpp] view plaincopy
  1. //建立一个保存元素为int的优先级队列，其实是建了一个小顶堆  
  2. //但是请特别注意这样的建的堆默认是大顶堆，即我们从堆顶去的元素是整个堆中元素最大的。  
  3.   
  4. priority_queue<int> Heap;  
  5.   
  6. //可以这样建一个表示小顶堆的优先级队列  
  7.   
  8. priority_queue<int , vector<int>, greater<int> > Heap;  
  9.   
  10. //将元素x放入优先级队列中  
  11.   
  12. Heap.push(x);  
  13.   
  14. //取出优先级队列第一个元素(堆顶元素),保存在x中  
  15.   
  16. int x = Heap.top();  
  17.   
  18. //弹出堆顶元素，取出后堆会自动调整为一个最小堆（最大堆）  
  19.   
  20. Heap.pop();  
  21.   
  22. //判断是否为空  
  23.   
  24. Heap.empty();  
  25.   
  26. //头文件  
  27.   
  28. #include<queue>  

<3>自定义优先级

添加元素为结构体需要重载‘<‘

[cpp] view plaincopy
  1. #include<iostream>  
  2. #include<stdio.h>  
  3. #include<queue>  
  4. using namespace std;  
  5.   
  6. struct Node    
  7. {    
  8.     //值  
  9.     int value;  
  10.     //编号  
  11.     int key;    
  12.     //重载操作符  
  13.     friend bool operator < (Node node1,Node node2)    
  14.     {      
  15.         //最大优先队列  
  16.         return node1.value < node2.value;    
  17.     }  
  18.     /* 
  19.     不要重载这个‘>‘只重载‘<‘ 
  20.     friend bool operator > (Node node1,Node node2)   
  21.     {   
  22.         return node1.value > node2.value;   
  23.     }  
  24.     */  
  25. };  
  26.   
  27. struct Node2    
  28. {    
  29.     //值  
  30.     int value;  
  31.     //编号  
  32.     int key;    
  33.     //重载操作符  
  34.     friend bool operator < (Node2 node1,Node2 node2)    
  35.     {      
  36.         //最小优先队列  
  37.         return node1.value > node2.value;    
  38.     }  
  39. };  
  40.   
  41. int main(){  
  42.     int i;  
  43.     //实例一 结构体1  
  44.     Node b[5];  
  45.     b[0].value = 6; b[0].key = 1;   
  46.     b[1].value = 9; b[1].key = 2;   
  47.     b[2].value = 2; b[2].key = 3;   
  48.     b[3].value = 8; b[3].key = 4;   
  49.     b[4].value = 1; b[4].key = 5;   
  50.     //最大优先队列  
  51.     priority_queue<Node> Heap;  
  52.     //入队列  
  53.     for(i = 0;i < 5;i++){  
  54.         Heap.push(b[i]);  
  55.     }  
  56.     printf("最大优先队列：\n");  
  57.     //出队列  
  58.     for(i = 0;i < 5;i++){  
  59.         printf("key:%d value:%d\n",Heap.top().key,Heap.top().value);  
  60.         Heap.pop();  
  61.     }  
  62.     //实例二 结构体2  
  63.     Node2 b2[5];  
  64.     b2[0].value = 6; b2[0].key = 1;   
  65.     b2[1].value = 9; b2[1].key = 2;   
  66.     b2[2].value = 2; b2[2].key = 3;   
  67.     b2[3].value = 8; b2[3].key = 4;   
  68.     b2[4].value = 1; b2[4].key = 5;   
  69.     //最大优先队列  
  70.     priority_queue<Node2> Heap2;  
  71.     //入队列  
  72.     for(i = 0;i < 5;i++){  
  73.         Heap2.push(b2[i]);  
  74.     }  
  75.     printf("最小优先队列：\n");  
  76.     //出队列  
  77.     for(i = 0;i < 5;i++){  
  78.         printf("key:%d value:%d\n",Heap2.top().key,Heap2.top().value);  
  79.         Heap2.pop();  
  80.     }  
  81.     return 0;  
  82. }  



注意：

[cpp] view plaincopy
  1. struct Node    
  2. {    
  3.     //值  
  4.     int value;  
  5.     //编号  
  6.     int key;    
  7.     friend bool operator > (Node node1,Node node2)    
  8.     {    
  9.         return node1.value > node2.value;    
  10.     }   
  11. };  

这样会报错。因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。



具体实例：点击打开链接

                   看病要排队

                   搬水果


联系
我们