【概念】
优先级队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。优先级队列是堆的一种常见应用。有最大优先级队列(最大堆)和最小优先级队列(最小堆)。优先级队列是一种维护有一组元素构成的集合S的数据结构。
【优先队列支持的基本运算】
-
-
-
-
priority_queue<int>Heap;
-
-
-
-
priority_queue<int,vector<int>,greater<int>>Heap;
-
-
-
-
Heap.push(x);
-
-
-
-
intx=Heap.top();
-
-
-
-
Heap.pop();
-
-
-
-
Heap.empty();
-
-
-
-
#include<queue>
【原理】
priority_queue调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。
用make_heap(), pop_heap(), push_heap()简单实现一个最大优先级队列
/*********************************
* 日期:2015-01-06
* 作者:SJF0115
* 题目: 简单实现最大优先级队列
* 博客:
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//简单实现最大优先级队列
template<typename T>
class priority_queue{
private:
// 数据
vector<T> data;
public:
// 进队列
void push(T val){
data.push_back(val);
push_heap(data.begin(),data.end());
}
// 出队列
void pop(){
pop_heap(data.begin(),data.end());
data.pop_back();
}
// 头元素
T top(){
return data.front();
}
// 大小
int size(){
return data.size();
}
// 是否为空
bool empty(){
return data.empty();
}
};
int main(){
priority_queue<char> heap;
heap.push('5');
heap.push('4');
heap.push('3');
heap.push('9');
heap.push('6');
while(!heap.empty()){
cout<<heap.top()<<endl;
heap.pop();
}//while
}
STL里面的 priority_queue 写法与此相似,只是增加了模板及相关的迭代器什么的。
priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数:
priority_queue<Type, Container, Functional>
其中Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。
Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list.
STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话,
优先队列就是大顶堆,队头元素最大。
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<char> heap;
heap.push('5');
heap.push('4');
heap.push('3');
heap.push('9');
heap.push('6');
// 输出最大优先级队列
while(!heap.empty()){
cout<<heap.top()<<endl;
heap.pop();
}//while
}
如果要用到小顶堆,则一般要把模板的三个参数都带进去。
STL里面定义了一个仿函数 greater<>,对于基本类型可以用这个仿函数声明小顶堆
#include <iostream>
#include <queue>
using namespace std;
int main(){
// 最小优先级队列
priority_queue<char,vector<char>,greater<char> > heap;
heap.push('5');
heap.push('4');
heap.push('3');
heap.push('9');
heap.push('6');
// 输出最大优先级队列
while(!heap.empty()){
cout<<heap.top()<<endl;
heap.pop();
}//while
}
对于自定义类型,则必须自己重载 operator< 或者自己写仿函数
【自定义优先级】
重载 operator<
-
#include<iostream>
-
#include<stdio.h>
-
#include<queue>
-
usingnamespacestd;
-
-
structNode
-
{
-
-
intvalue;
-
-
intkey;
-
-
friendbooloperator<(Nodenode1,Nodenode2)
-
{
-
-
returnnode1.value<node2.value;
-
}
-
-
-
-
-
-
-
-
};
-
-
structNode2
-
{
-
-
intvalue;
-
-
intkey;
-
-
friendbooloperator<(Node2node1,Node2node2)
-
{
-
-
returnnode1.value>node2.value;
-
}
-
};
-
-
intmain(){
-
inti;
-
-
Nodeb[5];
-
b[0].value=6;b[0].key=1;
-
b[1].value=9;b[1].key=2;
-
b[2].value=2;b[2].key=3;
-
b[3].value=8;b[3].key=4;
-
b[4].value=1;b[4].key=5;
-
-
priority_queue<Node>Heap;
-
-
for(i=0;i<5;i++){
-
Heap.push(b[i]);
-
}
-
printf("最大优先队列:\n");
-
-
for(i=0;i<5;i++){
-
printf("key:%dvalue:%d\n",Heap.top().key,Heap.top().value);
-
Heap.pop();
-
}
-
-
Node2b2[5];
-
b2[0].value=6;b2[0].key=1;
-
b2[1].value=9;b2[1].key=2;
-
b2[2].value=2;b2[2].key=3;
-
b2[3].value=8;b2[3].key=4;
-
b2[4].value=1;b2[4].key=5;
-
-
priority_queue<Node2>Heap2;
-
-
for(i=0;i<5;i++){
-
Heap2.push(b2[i]);
-
}
-
printf("最小优先队列:\n");
-
-
for(i=0;i<5;i++){
-
printf("key:%dvalue:%d\n",Heap2.top().key,Heap2.top().value);
-
Heap2.pop();
-
}
-
return0;
-
}
注意:
-
structNode
-
{
-
-
intvalue;
-
-
intkey;
-
friendbooloperator>(Nodenode1,Nodenode2)
-
{
-
returnnode1.value>node2.value;
-
}
-
};
这样会报错。因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
自定义类型重载 operator< 后,声明对象时就可以只带一个模板参数。
但此时不能像基本类型这样声明priority_queue<Node, vector<Node>, greater<Node> >;
原因是 greater<Node> 没有定义,如果想用这种方法定义则可以按如下方式:
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int value;
int key;
Node(int x,int y):key(x),value(y){}
};
struct cmp{
bool operator()(Node a,Node b){
if(a.key == b.key){
return a.value > b.value;
}
return a.key > b.key;
}
};
int main(){
priority_queue<Node,vector<Node>,cmp> heap;
Node node0(5,6);
Node node1(3,3);
Node node2(2,4);
Node node3(2,3);
Node node4(1,3);
heap.push(node0);
heap.push(node1);
heap.push(node2);
heap.push(node3);
heap.push(node4);
while(!heap.empty()){
Node node = heap.top();
cout<<"Key->"<<node.key<<" Value->"<<node.value<<endl;
heap.pop();
}//while
}
具体实例:点击打开链接
看病要排队
搬水果
分享到:
相关推荐
算法中优先级队列问题...用堆排序的算法来做的例子
用C++实现的优先级队列,对初学算法的同学能有所帮助
dheap(插入元素)、pop_max_dheap(删除最大元素)、pop_min_dheap(删除最小元素),is_dheap(堆验证)五个泛型算法,在此基础上实现了一个能在对数时间内获取最大和最小元素的优先级队列,相当于原stl优先级队列...
数据结构课设——小大根交替堆实现的双端优先级队列及应用 小大根交替堆是一种特殊的堆结构,它可以同时满足大根堆和小根堆的性质。在本文中,我们将对小大根交替堆实现的双端优先级队列进行详细的分析和设计。 ...
使用c++模板实现的堆排序、优先级队列,在vs2010下编译运行通过。压缩文件里为两个工程文件,如果有vs2010的话解压缩打开sln文件就可以了,没有的话,新建工程将文件复制过去就ok了。如果有问题可以留言。
数据结构与算法Python语言描述DS优先级队列和堆排序PPT学习教案.pptx
10.链式队列以及优先级队列应用.ppt
操作系统中的实验算法,多级反馈队列算法,静态优先级优先算法,用C或C++实现
在区分服务体系中优先级队列WFQ的节点调度策略约束下,兼顾负载均衡需求,提出了QoS路由度量标准DCB以及路由算法DCBR。仿真试验结果表明,该算法在实现最短时延的同时,提高了网络吞吐能力,并在时延抖动性能上得到...
该算法设置2个优先级队列,其中高优先级队列用于调度实时任务,低优先级队列用于调度非实时任务,高优先级队列中的任务可抢占低优先级队列中的任务。在此基础上,采用版本复制技术使系统具有容错能力,并分析了任务...
数据与算法:2基本数据结构7-优先级队列.pdf
数据结构与算法(Python语言描述)DS053优先级队列和堆排序ppt课件.ppt
二叉堆详解实现优先级队列.md
进程状态State (3)进程优先级改变原则 进程在就绪队列中呆一个时间片,优先级加1 进程运行一个时间片,优先级减3 (4)为了清楚的观察各进程的调度过程,程序应将每个时间片的进程的情况显示。出来
本文实例讲述了Python实现优先级队列的方法。分享给大家供大家参考,具体如下: 问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素; 解决方案:采用heapq模块...
本文件是对操作系统进程多级反馈队列调度算法的设计与实现,算法以txt的形式输入输出,其中包含设计报告
对于多队列,不同队列间具有不同的优先级,然而对于每队首元素又是采用动态的优先级定义。其中优先级有一定因素相关,这个不展开。
模拟动态优先级调度算法,程序内有详细的中文注释,方便理解。
将进程按照优先级分为多个队列:在多级反馈队列调度算法中,进程按照其优先级分为多个队列,每个队列拥有不同的时间片大小。 时间片动态调整:如果一个进程在当前队列中运行的时间超过了分配给它的时间片大小,但仍...