---

前言

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

一、补充内容：堆

1.1 什么是堆

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

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

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

1.2 堆的分类与性质

【分类】：

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

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

【性质】：

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

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

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

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

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

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

实现流程：

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

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

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

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

代码：

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定义与特点

1. 定义：仿函数本质上是一个类，它通过重载函数调用运算符（operator()）来模拟函数的行为。这样，类的实例就可以像函数一样被调用。
2. 特点：
   • 仿函数可以有参数和返回值，这是通过重载的operator()实现的。
   • 仿函数可以作为参数传递给其他函数，这是函数式编程和面向对象编程结合的一种体现。
   • 仿函数可以保存状态，因为它本质上是一个对象。这意味着在多次调用仿函数时，它可以保持一些内部状态不变，这对于实现某些复杂的算法和数据结构非常有用。

4.2 应用场景

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

4.3 实现方式

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

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

包含头文件：

#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