本文旨在深入剖析C++中优先队列的实现原理、核心特性及其底层机制,同时结合丰富的实战案例,帮助读者全面掌握优先队列的使用方法,并能够灵活应用于各种复杂问题的解决中。我们将从优先队列的基本概念出发,逐步深入到其内部实现细节,包括堆(Heap)结构的应用、比较函数的自定义等关键知识点。此外,本文还将探讨优先队列在解决经典算法问题中的实际应用,通过具体代码示例,展示如何在不同场景下发挥优先队列的最大效用
堆实际上就是一个完全二叉树,那么完全二叉树又是什么呢?
如图所示:这样大家就能更清晰明了的看出哪一个才是完全二叉树了吧
【分类】:
【性质】:
我们以小根堆来举例:
可以看到其中每一个分支都像是一个小根堆,父结点总是小于子结点
提问:为什么要设计这个算法?这个算法有什么用?
解释:众所周知,堆是一个数据结构,既然是数据结构,那必然离不开增删查改,假如我要删除堆的堆顶元素,为了不影响整个堆的结构,我们只能取最后一个元素放在堆顶,然后执行向下调整算法,直到整个堆变成我们想要的大根堆或是小根堆。或者说,当我们想要生成一个堆的时候,这种算法就有了明显的作用,举个例子:
**函数头:**如上图所示,我们要实现这样的函数,需要三个参数:
**函数体:**我们只需满足小根堆的性质即可
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1; // 左孩子和父节点的关系
while(child < n)
{
if(child + 1 < n && a[child + 1] < a[child])
{
++child;
}
if(a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}
同样的,我们需要在堆中插入一个元素的时候,我们只能将其插入至堆的末尾,然后逐步向上调整,直到得到我们想要的大根堆或是小根堆。
大致内容与向下调整算法类似,只是换了个方向比较,这里不再过多赘述。
**不同的是:**这里不需要判断左右孩子的大小,因为原本这就是一个小根堆,大小已经比较完了,如果新插入的元素小于父节点,那它必然小于左孩子
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while(child)
{
if(a[child] < a[parent])
{
swap(a[child], a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else break;
}
}
int n = sizeof(a) / sizeof(int);
//数组建堆算法
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(arr, n, i);
}
priority_queue
是 C++ 标准模板库(STL)中的一种容器适配器,它提供了队列的功能,并且其中元素的优先级可以由用户定义。默认情况下,priority_queue
是一个最大堆,即队列中每次出队(访问队首元素)的都是优先级最高的元素。如果你想实现一个最小堆,可以自定义比较函数或使用 greater
。
以下是 priority_queue
的一些基本用法和示例:
要使用 priority_queue
,你需要包含 <queue>
头文件:
#include <queue>
你可以使用默认的比较器来声明一个 priority_queue
,这样它会成为一个最大堆:
priority_queue<int> pq;
如果你想要一个最小堆,可以自定义比较器:
priority_queue<int, vector<int>, greater<int>> minHeap;
这里,vector<int>
是底层容器(虽然通常不需要显式指定,因为 priority_queue
默认使用 vector
),greater<int>
是比较器,用于确定元素的优先级。
以下是一个简单的示例,演示了如何使用 priority_queue
:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// 创建一个最大堆
priority_queue<int> maxHeap;
// 向最大堆中添加元素
maxHeap.push(10);
maxHeap.push(5);
maxHeap.push(20);
maxHeap.push(1);
// 输出并移除最大堆中的元素,直到堆为空
while (!maxHeap.empty()) {
cout << maxHeap.top() << " "; // 访问队首元素(优先级最高的元素)
maxHeap.pop(); // 移除队首元素
}
cout << endl;
// 创建一个最小堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 向最小堆中添加元素
minHeap.push(10);
minHeap.push(5);
minHeap.push(20);
minHeap.push(1);
// 输出并移除最小堆中的元素,直到堆为空
while (!minHeap.empty()) {
cout << minHeap.top() << " "; // 访问队首元素(优先级最低的元素)
minHeap.pop(); // 移除队首元素
}
cout << endl;
return 0;
}
在这个示例中,我们首先创建了一个最大堆,并向其中添加了一些整数。然后,我们循环输出并移除最大堆中的元素,直到堆为空。接着,我们创建了一个最小堆,并重复了相同的操作。
注意,priority_queue
不支持直接访问或修改除队首元素以外的其他元素,也不支持随机访问。
废话不多说我们直接开造!!!
namespace xny
{
template <class T, class Container = vector<T>>
class my_priority_queue
{
public:
my_priority_queue(){}
template <class InputIterator>
my_priority_queue(InputIterator first, InputIterator last);
bool empty();
size_t size();
T& top();
void push(const T& x);
void pop();
private:
Container c;
};
}
在此之前,我们已经声明优先队列实际上就是一个大根堆,也就是说初始化我们需要用堆的方式进初始化,所以我们应该增添一个函数在类的private内部:
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < c.size()) {
if (child + 1 < c.size() && c[child + 1] < c[child]) {
++child;
}
if (c[child] < c[parent]) {
swap(c[child], c[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
在之前已经分析过,这里就不再过多赘述,唯一不同的就是参数变少了,原因是类的内部已经提供了这些东西,可以直接用
迭代器范围构造函数:
template <class InputIterator>
my_priority_queue(InputIterator first, InputIterator last) {
while (first != last) {
c.push_back(*first);
++first;
}
// 堆的初始化
for (int i = (size() - 1 - 1) / 2; i > 0; --i) {
AdjustDown(i);
}
}
bool empty() const {
return c.empty();
}
size_t size() const {
return c.size();
}
T& top() {
return c[0];
}
向上调整算法:
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child) {
if (c[child] < c[parent]) {
swap(c[child], c[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
push:
void push(const T& x) {
c.push_back(x);
AdjustUp(c.size() - 1);
}
pop:
解释:上面我们提到,为了不影响整个堆的结构,我们只能先交换堆顶和堆尾元素,再删除交换前的堆顶元素,然后执行向下调整算法,直到整个堆变成我们想要的大根堆或是小根堆。
void pop() {
swap(c[0], c[c.size() - 1]);
c.pop_back();
AdjustDown(0);
}
这里为什么我们要说仿函数这个东西呢?可以发现我们上述模拟实现的只是固定的一个大根堆的优先队列,但是标准库里通过传参数的不同还能实现小根堆的优先队列,这里就是用了仿函数,下面我来介绍一下仿函数的基本要点:
下面我就来为大家实现仿函数在堆里的实现:
包含头文件:
#include<functional>
仿函数体:
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) {
return x < y;
}
};
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) {
return x > y;
}
};
然后我们的类模板参数就应该变成这样了:
template <class T, class Container = vector<T>, class Compare = Less<T>>
或者:
template <class T, class Container = vector<T>, class Compare = Greater<T>>
#pragma once
#include<vector>
#include<functional>
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) {
return x < y;
}
};
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) {
return x > y;
}
};
namespace xny
{
template <class T, class Container = vector<T>, class Compare = Less<T>>
class my_priority_queue
{
private:
// 向下调整堆
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < c.size()) {
if (comp(child + 1, c.size()) && comp(c[child + 1], c[child])) {
++child;
}
if (comp(c[child], c[parent])) {
swap(c[child], c[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
// 向上调整堆
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child) {
if (comp(c[child], c[parent])) {
swap(c[child], c[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
public:
my_priority_queue(){}
template <class InputIterator>
my_priority_queue(InputIterator first, InputIterator last) {
while (first != last) {
c.push_back(*first);
++first;
}
for (int i = (size() - 1 - 1) / 2; i > 0; --i) {
AdjustDown(i);
}
}
bool empty() const {
return c.empty();
}
size_t size() const {
return c.size();
}
T& top() {
return c[0];
}
void push(const T& x) {
c.push_back(x);
AdjustUp(c.size() - 1);
}
void pop() {
swap(c[0], c[c.size() - 1]);
c.pop_back();
AdjustDown(0);
}
private:
Container c;
Compare comp;
};
void test_my_priority_queue()
{
my_priority_queue<int> q;
q.push(1);
q.push(2);
q.push(5);
q.push(6);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.top() << " ";
q.pop();
}
cout << endl;
}
}
代码:
#include <iostream>
#include <queue>
using namespace std;
#include "my_priority"
int main()
{
xny::test_my_priority_queue();
return 0;
}
输出:
1 2 3 4 5 6
今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,17的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是17前进的动力!