<1>概念
优先级队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。优先级队列是堆的一种常见应用。有最大优先级队列(最大堆)和最小优先级队列(最小堆)。优先级队列是一种维护有一组元素构成的集合S的数据结构。
<2>优先队列支持的基本运算
-
-
-
-
priority_queue<int> Heap;
-
-
-
-
priority_queue<int , vector<int>, greater<int> > Heap;
-
-
-
-
Heap.push(x);
-
-
-
-
int x = Heap.top();
-
-
-
-
Heap.pop();
-
-
-
-
Heap.empty();
-
-
-
-
#include<queue>
<3>自定义优先级
添加元素为结构体需要重载‘<‘
-
#include<iostream>
-
#include<stdio.h>
-
#include<queue>
-
using namespace std;
-
-
struct Node
-
{
-
-
int value;
-
-
int key;
-
-
friend bool operator < (Node node1,Node node2)
-
{
-
-
return node1.value < node2.value;
-
}
-
-
-
-
-
-
-
-
};
-
-
struct Node2
-
{
-
-
int value;
-
-
int key;
-
-
friend bool operator < (Node2 node1,Node2 node2)
-
{
-
-
return node1.value > node2.value;
-
}
-
};
-
-
int main(){
-
int i;
-
-
Node b[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:%d value:%d\n",Heap.top().key,Heap.top().value);
-
Heap.pop();
-
}
-
-
Node2 b2[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:%d value:%d\n",Heap2.top().key,Heap2.top().value);
-
Heap2.pop();
-
}
-
return 0;
-
}
注意:
-
struct Node
-
{
-
-
int value;
-
-
int key;
-
friend bool operator > (Node node1,Node node2)
-
{
-
return node1.value > node2.value;
-
}
-
};
这样会报错。因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
具体实例:点击打开链接
看病要排队
搬水果
经典白话算法之优先级队列,布布扣,bubuko.com
经典白话算法之优先级队列
原文:http://blog.csdn.net/sunnyyoona/article/details/24903699