在前面，我们已经分享完队列的基本内容，现在我们来看看队列衍生出来的一种数据结构——优先队列。优先队列行为像队列，但先出队列的元素不是先进队列的元素，而是队列中优先级最高的元素。优先队列是与堆，树相结合的一种数据结构。下面一起来看看吧
1.概念
优先队列可以插入元素、查询最大值、删除最大值。优先队列其实就是最大堆或最小堆，最大堆可以用来实现最大优先队列，最小堆可以用来实现最小优先队列。用各种堆都可以实现优先队列。优先队列分为几种，下面一起来看看吧
2，分类
（一）.STL优先队列
注意：优先队列如果要自定义排序函数，只能用仿函数，不能用普通函数的指针。优先队列是一类容器适配器，特地被设计满足该容器的第一个元素按照没有严格弱序排序，总是所有元素中最大的。
在说STL优先队列前，先介绍一下：priority_queue
priority_queue 的模板参数:
template
class Compare = less
T：元素类型。
Container：低层存储容器类型，默认为vector< T >类型。
Compare：两个参数且返回值为bool类型的双参判断式，默认为less< T >判断式。
priority_queue自定数据类型和自定义排序方式
1.使用自定义类型比较关系
即重载数据类型Node的 < 、>运算符，使得Node类型的对象可以使用<，>符号进行比较。代码如下：
struct Node {
int size;
int price;
// 重载<运算符
bool operator<(const Node &b) const {
return this->size == b.size ? this->price > b.price : this->size < b.size;
}
};
int main() {
priority_queue
for (int i = 0; i < 5; i++) {
priorityQueue.push(Node{i, 5 - i});
}
while (!priorityQueue.empty()) {
Node top = priorityQueue.top();
cout << "size:" << top.size << " price:" << top.price << endl;
priorityQueue.pop();
}
return 0;
}
输出结果：
size:4 price:1
size:3 price:2
size:2 price:3
size:1 price:4
size:0 price:5
由于priority_queue中默认使用less
struct Node {
int size;
int price;
// 重载>运算符
bool operator>(const Node &b) const {
return this->size == b.size ? this->price < b.price : this->size > b.size;
}
};
2.使用仿函数（函数对象）
使用仿函数（函数对象）作为Compare双参判断式。代码如下：
struct Node {
int size;
int price;
};
class Cmp {
public:
bool operator()(const Node &a, const Node &b) {
return a.size == b.size ? a.price > b.price : a.size < b.size;
}
};
int main() {
priority_queue
for (int i = 0; i < 5; i++) {
priorityQueue.push(Node{i, 5 - i});
}
while (!priorityQueue.empty()) {
Node top = priorityQueue.top();
cout << "size:" << top.size << " price:" << top.price << endl;
priorityQueue.pop();
}
return 0;
}
输出结果：
size:4 price:1
size:3 price:2
size:2 price:3
size:1 price:4
size:0 price:5
需要注意的是：使用仿函数对优先队列进行自定义排序，需要在声明priority_queue对象时显式地定义Container类型和Compare类型，即:
priority_queue
3.使用lambda表达式，不是很重要，这里就不多说了
4.函数指针
使用函数指针与3. 使用lambda表达式类似，都是在priority_queue<.,.,Cmp>中定义Compare的类型同时在priorityQueue(cmp)的中输入具体的对象作为参数，不过 这里使用的是函数和函数的指针（地址）而不是lambda表达式对象。例子如下:
bool cmpFun(const Node &a, const Node &b) {
return a.size == b.size ? a.price > b.price : a.size < b.size;
}
bool (*p)(const Node &, const Node &) = cmpFun;
priority_queue
实例：
#include
#include
#include
using namespace std;
class cmp
{
public:
bool operator()(int a, int b)
{
return a < b;
}
};
bool cmp2(int a, int b)
{
return a < b;
}
template
void display()
{
A q;
q.push(1);
q.push(3);
q.push(4);
q.push(2);
while (!q.empty())
{
cout << q.top();
q.pop();
}
cout << endl;
}
int main()
{
display < priority_queue
display < priority_queue
display < priority_queue
display < priority_queue
//display < priority_queue
return 0;
}
输出结果：
4321
1234
4321
4321
二.二叉堆实现优先队列
二叉堆其实就是一种特殊的二叉树(完全二叉树)，只不过存储在数组里。（所以我们的排序过程应该是在数组中原地进行的）。一般的链表二叉树，我们操作节点的指针，而在数组里，我们用数组的索引当作指针即可。例子：
#include
#include
using namespace std;
template
bool cmp(T a, T b)
{
return a < b; //最大堆
}
template
void exchange(T* a, T* b)
{
T tmp = *a;
*a = *b;
*b = tmp;
}
int LeftChild(int id)
{
return id * 2;
}
int RightChild(int id)
{
return id * 2 + 1;
}
int Parent(int id)
{
return id/2;
}
template
void AdjustHeap(T* arr, int rootId, int size)
{
int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
if (left < size && cmp(arr[largest], arr[left]))largest = left;
if (right < size && cmp(arr[largest], arr[right]))largest = right;
if (largest == rootId)return;
exchange(arr + rootId, arr + largest);
AdjustHeap(arr, largest, size);
}
template
void HeapIncrese(T* arr, int size, int id, T newValue)
{
arr[id] = newValue;
while (id > 0 && cmp(arr[Parent(id)], arr[id])) {
exchange(arr + id, arr + Parent(id));
id = Parent(id);
}
}
template
void HeapInsert(T* arr, int &size,T value)
{
HeapIncrese(arr,size+1,size,value);
size++;
}
int g_size;
void Init()
{
g_size = 0;
}
template
T Top(T* arr)
{
return arr[0];
}
template
void Push(T* arr, T value)
{
HeapInsert(arr,g_size,value);
}
template
void Pop(T* arr)
{
g_size--;
exchange(arr, arr+g_size);
AdjustHeap(arr, 0, g_size);
}
int main()
{
int q[10];
Init();
Push(q,4);
Push(q,2);
Push(q,6);
Push(q,3);
Push(q,4);
Push(q,5);
cout<
cout<
cout<
cout<
cout<
cout<
cout<
}
运行结果：6 5 4 4 3 2 0
三,二项堆实现优先队列。二项堆（Binomial Heap）是二项树（Binomial Tree）的集合
四.线段树实现优先队列
实例：
struct anode
{
int t;
int d;
};
int n;
int num[10001],maxx[40001];
struct anode node[10001];
void build(int key, int low, int high)//id
{
if (low == high)
{
maxx[key] = low;
return;
}
int mid = (low + high) / 2;
build(key * 2, low, mid);
build(key * 2 + 1, mid + 1, high);
maxx[key] = (num[maxx[key * 2]] > num[maxx[key * 2 + 1]]) ? maxx[key * 2] : maxx[key * 2 + 1];
}
void update(int key, int low, int high, int uplace)//id
{
if (low == high)
{
maxx[key] = low;
return;
}
int mid = (low + high) / 2;
if (uplace <= mid)update(key * 2, low, mid, uplace);
else update(key * 2 + 1, mid + 1, high, uplace);
maxx[key] = (num[maxx[key * 2]] > num[maxx[key * 2 + 1]]) ? maxx[key * 2] : maxx[key * 2 + 1];
}
int query(int key, int low, int high, int x, int y)//id
{
if (low == x && high == y)return maxx[key];
int mid = (low + high) / 2;
if (mid < x)return query(key * 2 + 1, mid + 1, high, x, y);
if (mid >= y)return query(key * 2, low, mid, x, y);
int a = query(key * 2, low, mid, x, mid);
int b = query(key * 2 + 1, mid + 1, high, mid + 1, y);
return (num[a]>num[b]) ? a : b;
}
void push(int loc)
{
num[loc]=node[loc].t; ///根据实际情况修改
update(1,1,n,loc);
}
void pop(int loc)
{
num[loc]=0; ///根据实际情况修改
update(1,1,n,loc);
}
int top()//id
{
return query(1,1,n,1,n);
}
好啦，关于优先队列的知识就分享到这啦
本贴为博主亲手整理。如有错误，请评论区指出，一起进步。谢谢大家的浏览.
