定义
优先队列是一种抽线数据类型，优先队列中的每个元素都有优先级，优先级高的先出队，而优先级相同的则按照入队的顺序出队。优先队列往往通过二叉堆来实现。
二叉堆的性质
- 根节点元素值始终大于/小于左右节点的值
- 完全二叉树
使用二叉堆实现优先队列
二叉堆通常使用数组来表示，下图展示了如何使用数组来表示二叉堆
构建最大堆类
根据根节点元素的值小于或者大于左右节点的值，可以分为最小堆（小顶堆）或者最大堆（大顶堆），主要区别在于堆顶是最小值还是最大值。
优先队列存在从堆尾插入元素和删除堆顶元素两种操作方法，因此具体的类实现如下：
class MaxPQ
{
// 成员变量
vector<int> pq; // 用于存储大顶堆的元素
int N = 0; // 当前堆包含的元素个数
public:
MaxPQ(int cap)
{
// 开辟空间
pq.resize(cap + 1); // 序号为0不存储元素
}
// 返回当前队列中最大元素
int max()
{
return pq[1];
}
// 插入元素e，即将元素e添加到队尾，然后上浮到合适的位置
void insert(int e);
// 删除并返回当前队列中最大元素
int delMax();
// 上浮第k个元素，以维护最大堆的性质
void swim(int k);
// 下沉第k个元素，以维护最大堆性质
void sink(int k);
// 交换数组的两个元素
void exch(int i, int j)
{
int temp = pq[j];
pq[j] = pq[i];
pq[i] = temp;
}
// 判断pq[i] 是否比pq[j]小
bool less(int i, int j)
{
return pq[i] < pq[j] ? true : false;
}
// 返回当前节点父节点索引
int parent(int root)
{
return root / 2;
}
// 返回左子节点的索引
int left(int root)
{
return 2 * root;
}
int right(int root)
{
return 2 * root + 1;
}
};
实现swim和sink函数
从子节点的角度来看，如果某个节点A比他的父节点B大，那么A不应该在子节点，而应该把A节点上浮把父节点B换下来，自己做父节点。
void MaxPQ::swim(int k)
{
// 给的节点与父节点相比
while(k > 1 && less(parent(k), k))
{
// 交换节点
exch(parent(k), k);
k = parent(k);
}
}
从父节点的角度来看，如果父节点A与其两个子节点比较大小，如果A不是最大的就需要调整位置，进行下沉把较大的子节点和A交换。
void MaxPQ::sink(int k)
{
// 如果沉到堆底，就不下沉了
while(left(k) <= N)
{
// 先假设左边节点较大,返回左边节点的索引
int maxer = left(k);
// 如果右边节点存在，比一下大小
if(right(k) <= N && less(maxer, right(k))
{
maxer = right(k);
}
// 如果节点k比两个孩子都大，就不必下称了
if(less(maxer, k)) break;
exch(k, maxer);
k = maxer;
}
}
队尾插入元素
思路：从队尾插入节点N，然后将节点N上浮到合适的位置。
void MaxPQ::insert(int e)
{
N++;
// 把先添加的元素查到最后
pq[N] = e;
// 让它上浮到正确的位置
swim(N);
}
删除队顶最大元素
思路：先将堆顶元素A和堆底元素B进行交换，然后删除元素A，最后让元素B下沉到合适的位置
int MaxPQ::delMax()
{
int max = pq[1];
// 交换
exch(1, N);
pq[N] = NULL;
N--;
// 让B下沉
sink(1);
return max;
}
测试
#include <iostream>
#include <vector>
using namespace std;
class MaxPQ
{
private:
// 存储元素的数组
vector<int> pq;
// 当前PQ中的元素个数
int N ;
public:
// 构造函数
MaxPQ(int capacity)
{
// 索引0不用，所以需要多分配一个空间
pq.resize(capacity + 1);
N = 0;
}
// 返回当前队列中最大元素
int max()
{
return pq[1];
}
// 插入元素
void insert(int e)
{
// 将要插入的元素添加到堆底的位置，然后上浮到正确位置
++N;
// 先将新的元素添加到最后
pq[N] = e;
// 然后上浮到正确位置
swim(N);
}
// 删除并返回当前数组中最大元素
int delMax()
{
// 先将堆顶的元素A和堆底元素B位置对调，然后删除A，将B下沉到合适位置
int max = pq[1];
// 兑换
exch(1, N);
// 删除
--N;
// 下称
sink(1);
return max;
}
/* ******************* helper functions ********************* */
int parent(int root)
{
return root / 2;
}
int left(int root)
{
return root * 2;
}
int right(int root)
{
return root * 2 + 1;
}
// 上浮第k个元素，以维护最大堆性质
void swim(int k) // 定位为子节点
{
// 如果某个节点A比它的父节点大，那么对A上浮
while(k > 1 && less(parent(k), k)) // k> 1才有父节点
{
cout << "swin: " << pq[k] << endl;
// 交换序号为parent(k) 和 k 的值
exch(parent(k), k);
// 交换完后k位于父节点处
k = parent(k);
}
}
// 下沉第k个元素
void sink(int k) // 定位为父节点
{
// 如果某个节点A比它的子节点小，则对A下沉
// 需要判断A与其两个子节点比较大小，判断A是否为最大值
while(left(k) <= N)
{
// 先假设左节点为最大值
int older = left(k);
// 如果右节点存在，比较大小
while(right(k) <= N && less(left(k), right(k)))
{
// 最大值为右节点
older = right(k);
}
// 父节点与最大子节点进行比较
if(less(older, k)) break;
// 否则交换并下沉k节点
cout << "sink: " << pq[k] << endl;
exch(older, k);
k = older;
}
}
// 交换数组的两个元素
void exch(int i, int j)
{
// cout << "i: " << i << " j: " << j << endl;
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
// 比较pq[i]是否小于pq[j]
bool less(int i, int j)
{
return pq[i] < pq[j];
}
};
int main()
{
MaxPQ data(10);
data.insert(2);
data.insert(5);
data.insert(6);
data.insert(10);
data.delMax();
cout << data.max() << endl;
return 0;
}
C++中优先队列的使用
priority_queue在C++的queue库中实现，优先队列的底层实现是heap堆，可以在任意时刻从堆底插入元素，但是只可以访问堆顶元素。提供了如下一些成员函数：
- empty()：判断是否为空
- size()：返回优先队列中元素的个数
- top()：堆顶 access top element
- push(): insert element
- pop(): remove top element
- swap(): 交换内容
类定义
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
与stack和queue类似，priority_queue也是container adaptor，设计用来保证队顶元素为最大值。
- Type：所有元素的数据类型
- Container： vector和dequeue可以作为底层的容器，默认情况下，使用vector
- compare：排序函数，可以是一个函数pointer或者函数object
//最小堆
priority_queue <int,vector<int>,greater<int> > q;
//最大堆
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
1. 使用基础类型
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
priority_queue<int> a; // 默认为最大堆
a.push(3);
a.push(1);
a.push(6);
while (!a.empty())
{
cout << a.top() << '\n';
a.pop();
}
}
2. 使用pair
对于用户自定义的数据结构，常见有两种比较规则来初始化priority_queue对象，一个是重载小于运算符，另一个是使用重载函数操作符的类对象。在2. 使用pair中介绍了重载（）的方法，在3.使用自定义类型中介绍了小于运算符重载的方法
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 重载()符号
typedef struct
{
bool operator() (const pair<int, int>& a, const pair<int, int>& b)
{
// 最大堆
return a.second < b.second;
// 最小堆
// return a.second > b.second;
}
}cmp;
int main()
{
priority_queue< pair<int, int>, vector<pair<int, int>>, cmp > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty())
{
cout << a.top().first << ' ' << a.top().second << '\n';
a.pop();
}
}
3. 使用自定义类型
#include <iostream>
#include <queue>
using namespace std;
typedef struct Exp1
{
// 运算符重载
int data;
Exp1(int a) { data = a;}
bool operator<(const Exp1& a) const
{
return data < a.data; // <待参考值，比较值>
}
} EXP1;
int main()
{
Exp1 a(1);
Exp1 b(2);
Exp1 c(4);
priority_queue<Exp1> d;
d.push(a);
d.push(c);
d.push(b);
while(!d.empty())
{
cout << "top: " << d.top().data << " ";
d.pop();
}
cout << endl;
}
参考链接
- https://cloud.tencent.com/developer/article/1695851
- https://blog.csdn.net/liu2012huan/article/details/52932494
- https://cplusplus.com/reference/queue/priority_queue/priority_queue/
版权声明：本文为hello_dear_you原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。