文章目录

前言🧁一、补充内容：堆1.1 什么是堆1.2 堆的分类与性质1.3 堆的向下调整算法（小根堆）实现流程：代码：

1.4 堆的向上调整算法（小根堆）实现流程：代码：

1.5 数组建堆算法实现（小根堆）

🧁二、优先队列priority_queue的使用2.1 引入头文件2.2 基本声明2.3 常用操作2.4 示例代码

🧁三、priority_queue的模拟实现3.1 基本框架3.2 迭代器范围构造函数3.3 基本函数3.4 push与pop函数（重点）

🧁四、仿函数4.1定义与特点4.2 应用场景4.3 实现方式

🧁五、优化后的全部代码5.1 头文件（包含测试函数）5.2 源文件

结语

前言

本文旨在深入剖析C++中优先队列的实现原理、核心特性及其底层机制，同时结合丰富的实战案例，帮助读者全面掌握优先队列的使用方法，并能够灵活应用于各种复杂问题的解决中。我们将从优先队列的基本概念出发，逐步深入到其内部实现细节，包括堆（Heap）结构的应用、比较函数的自定义等关键知识点。此外，本文还将探讨优先队列在解决经典算法问题中的实际应用，通过具体代码示例，展示如何在不同场景下发挥优先队列的最大效用

🧁一、补充内容：堆

1.1 什么是堆

堆实际上就是一个完全二叉树，那么完全二叉树又是什么呢？

假如一个二叉树有k层，并且这个树的前k-1层都是满树，第k层的叶子结点全部集中紧挨着在左边，举个例子：

如图所示：这样大家就能更清晰明了的看出哪一个才是完全二叉树了吧

1.2 堆的分类与性质

【分类】：

堆分为两类：1. 大根堆，2. 小根堆

那么这两种堆的区别在哪呢？故名思义：大根堆的堆顶代表整个堆最大的元素，小根堆的堆顶代表整个堆最小的元素

【性质】：

大根堆的左右子树都是大根堆，小根堆的左右子树都是小根堆堆中的结点总是不大于或不小于其父结点

我们以小根堆来举例：

可以看到其中每一个分支都像是一个小根堆，父结点总是小于子结点

1.3 堆的向下调整算法（小根堆）

提问：为什么要设计这个算法？这个算法有什么用？

解释：众所周知，堆是一个数据结构，既然是数据结构，那必然离不开增删查改，假如我要删除堆的堆顶元素，为了不影响整个堆的结构，我们只能取最后一个元素放在堆顶，然后执行向下调整算法，直到整个堆变成我们想要的大根堆或是小根堆。或者说，当我们想要生成一个堆的时候，这种算法就有了明显的作用，举个例子：

我们定义一个数组arr，想要将其变成一个小根堆

实现流程：

**函数头：**如上图所示，我们要实现这样的函数，需要三个参数：

数组地址数组元素个数即堆的结点个数向下调整的起始位置，应该默认是0，即根结点

**函数体：**我们只需满足小根堆的性质即可

跳出循环遍历的条件：遍历完所有结点父节点总是与左右孩子较小的一个比较如果子结点小于父结点，交换父子结点，继续遍历比较，否则跳出循环

代码：

<code>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;

}

}

1.4 堆的向上调整算法（小根堆）

同样的，我们需要在堆中插入一个元素的时候，我们只能将其插入至堆的末尾，然后逐步向上调整，直到得到我们想要的大根堆或是小根堆。

实现流程：

大致内容与向下调整算法类似，只是换了个方向比较，这里不再过多赘述。

**不同的是：**这里不需要判断左右孩子的大小，因为原本这就是一个小根堆，大小已经比较完了，如果新插入的元素小于父节点，那它必然小于左孩子

代码：

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;

}

}

1.5 数组建堆算法实现（小根堆）

若左右子树不是小堆——想办法把左右子树处理成小堆

可以从倒数第一个非叶子节点的位置开始向下调整

最后一个非叶子节点的下标为 (n-1-1)/2

int n = sizeof(a) / sizeof(int);

//数组建堆算法

for (int i = (n - 1 - 1) / 2; i >= 0; --i)

{

AdjustDown(arr, n, i);

}

🧁二、优先队列priority_queue的使用

priority_queue 是 C++ 标准模板库（STL）中的一种容器适配器，它提供了队列的功能，并且其中元素的优先级可以由用户定义。默认情况下，priority_queue 是一个最大堆，即队列中每次出队（访问队首元素）的都是优先级最高的元素。如果你想实现一个最小堆，可以自定义比较函数或使用 greater。

以下是 priority_queue 的一些基本用法和示例：

2.1 引入头文件

要使用 priority_queue，你需要包含 <queue> 头文件：

#include <queue>

2.2 基本声明

你可以使用默认的比较器来声明一个 priority_queue，这样它会成为一个最大堆：

priority_queue<int> pq;

如果你想要一个最小堆，可以自定义比较器：

priority_queue<int, vector<int>, greater<int>> minHeap;

这里，vector<int> 是底层容器（虽然通常不需要显式指定，因为 priority_queue 默认使用 vector），greater<int> 是比较器，用于确定元素的优先级。

2.3 常用操作

push(x): 向队列中添加一个元素。pop(): 移除队首元素（优先级最高的元素）。top(): 返回队首元素的引用（但不移除它）。empty(): 检查队列是否为空。size(): 返回队列中元素的数量。

2.4 示例代码

以下是一个简单的示例，演示了如何使用 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 不支持直接访问或修改除队首元素以外的其他元素，也不支持随机访问。

🧁三、priority_queue的模拟实现

废话不多说我们直接开造！！！

3.1 基本框架

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;

};

}

3.2 迭代器范围构造函数

在此之前，我们已经声明优先队列实际上就是一个大根堆，也就是说初始化我们需要用堆的方式进初始化，所以我们应该增添一个函数在类的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);

}

}

3.3 基本函数

bool empty() const {

return c.empty();

}

size_t size() const {

return c.size();

}

T& top() {

return c[0];

}

3.4 push与pop函数（重点）

值得注意的是，堆的插入，可不仅仅是把值插入到尾端就结束了，不要忘了堆的性质，在插入之后我们就需要用到堆的向上调整算法，将堆的结构还原

向上调整算法：

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);

}

🧁四、仿函数

这里为什么我们要说仿函数这个东西呢？可以发现我们上述模拟实现的只是固定的一个大根堆的优先队列，但是标准库里通过传参数的不同还能实现小根堆的优先队列，这里就是用了仿函数，下面我来介绍一下仿函数的基本要点：

4.1定义与特点

定义：仿函数本质上是一个类，它通过重载函数调用运算符（operator()）来模拟函数的行为。这样，类的实例就可以像函数一样被调用。特点：

仿函数可以有参数和返回值，这是通过重载的operator()实现的。仿函数可以作为参数传递给其他函数，这是函数式编程和面向对象编程结合的一种体现。仿函数可以保存状态，因为它本质上是一个对象。这意味着在多次调用仿函数时，它可以保持一些内部状态不变，这对于实现某些复杂的算法和数据结构非常有用。

4.2 应用场景

STL算法：在C++的标准模板库（STL）中，许多算法如sort、for_each、transform等都接受仿函数作为参数。这允许程序员自定义排序规则、操作、条件等。自定义容器：通过仿函数，可以实现具有特定行为的自定义容器。例如，可以定义一个堆栈容器，该容器在每次弹出元素时都返回最小的元素。函数对象传递：仿函数可以用作函数的参数或返回值，实现更灵活的函数调用和传递。

4.3 实现方式

重载operator()：要在类中实现仿函数的功能，只需重载()运算符即可。在该运算符的实现中，可以包含任何需要的逻辑和状态。使用模板：仿函数通常与模板一起使用，以实现更通用的代码。通过模板参数，可以灵活地传递不同类型的仿函数。

下面我就来为大家实现仿函数在堆里的实现：

包含头文件：

#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>>

🧁五、优化后的全部代码

5.1 头文件（包含测试函数）

#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;

}

}

5.2 源文件

代码：

#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前进的动力！