目录

一、priority_queue的认识

priority_queue 是 C++ STL 提供的一种容器适配器，本质上依赖底层容器（默认是 vector）来存储数据，并通过堆的方式来维护元素顺序，它和普通队列不同，不是“先来先走”，而是按照优先级大小决定谁先出来；其中第一个模板参数（class T） 表示存储的数据类型，第二个模板参数（class Container = vector） 决定底层用什么容器，第三个参数则定义比较规则 默认是大顶堆，即数值大的优先级高，也可以改成小顶堆）；因此，它最大的特点就是无论插入多少元素，每次取出的都是当前优先级最高的那个，非常适合用在需要频繁获取极值的场景，比如贪心算法、最短路径、任务调度等，你可以把它想象成一个“VIP 排队窗口”，永远让最重要的人排在最前面。

---

二、priority_queue的使用

1. 定义方式

1.1 大堆

储存数据类型为int，容器为vector，构造大堆。

代码语言：javascript

AI代码解释

priority_queue<int, vector<int>, less<int>> q1;

---

1.2 小堆

储存数据类型为int，容器为vector，构造小堆。

代码语言：javascript

AI代码解释

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

---

1.3 不指定

不指定数据类型，容器，和内部需要构造的堆。

代码语言：javascript

AI代码解释

priority_queue<int> q;

注意： 此时默认使用vector底层容器，内部默认为大堆。

---

2. priority_queue各个接口的使用

2.1 表格

接口	作用	说明
empty()	判断队列是否为空	为空返回 true，否则返回 false
size()	返回队列中元素个数	常用于统计当前优先级队列的规模
top()	访问队头元素	获取优先级最高的元素（但不删除），复杂度 O(1)
push(x)	插入元素 x	会自动调整堆结构，复杂度 O(log n)
pop()	删除队头元素	移除当前优先级最高的元素，复杂度 O(log n)
swap(q)	交换两个队列的内容	与另一个优先级队列整体交换数据

---

2.2 示例

代码语言：javascript

AI代码解释

#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int main()
{
	priority_queue<int> q;
	q.push(5);
	q.push(2);
	q.push(0);
	q.push(1);
	q.push(3);
	q.push(1);
	q.push(4);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl; //5 4 3 2 1 1 0
	return 0;
}

---

三、priority_queue的模拟实现

以下堆的调整算法均以大堆为例

1. 堆的向上调整算法

大堆为例，堆的向上调整算法就是在大堆的末尾插入一个数据后，经过一系列的调整，使其仍然是一个大堆。

主要思路：

1. 将我们想要插入的数据和它的父节点进行比较，如果大于其父节点就和父节点交换，以此类推，直到插入的数据比其父节点小则停止交换；
2. 和父节点交换后我们需要将父节点的下标赋值给需要插入的数据，然后重新计算这个插入数据的父节点。

---

我们想在大堆的末尾插入一个新的数据：96

在这里插入图片描述

经过我们的调整应该为：

在这里插入图片描述

代码语言：javascript

AI代码解释

    void adjust_up(int child)
    {
        int parent = (child - 1) / 2; //求父节点
        while(child > 0) //只要没到根节点，继续调整
        {
            if (_con[parent] < _con[child])//父节点小于子节点
            {
                swap(_con[parent], _con[child]);//交换

                child = parent;//将父节点作为新的子节点，继续往上比较
                parent = (child - 1) / 2;//更新父节点
            }
            else
            {
                break;
            }
        }
    }

---

2. 堆的向下调整算法

以大堆为例，使用堆的向下调整算法有一个前提，就是待向下调整的结点的左子树和右子树必须都为大堆。

在这里插入图片描述

主要思路：

1. 将目标结点与其较大的子结点进行比较。
2. 若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整；若目标结点的值比其较大子结点的值大，则停止向下调整，此时该树已经是大堆了。

在这里插入图片描述

代码语言：javascript

AI代码解释

// 大顶堆的向下调整
void adjust_down(int parent)
{
    // 先找到 parent 的左孩子下标
    int child = parent * 2 + 1; // 左孩子 = 2*parent + 1

    // 只要 child 没越界，就继续比较
    while (child < _con.size())
    {
        // 如果右孩子存在，并且右孩子比左孩子大，
        // 那么让 child 指向右孩子（因为要和更大的孩子比较）
        if (child + 1 < _con.size() && _con[child] < _con[child + 1])
        {
            child++;
        }

        // 如果父节点比孩子小，就交换
        if (_con[parent] < _con[child])
        {
            swap(_con[parent], _con[child]);
        }
        else
        {
            // 父节点已经比孩子大了，说明局部已经是大顶堆，结束循环
            break;
        }

        // 交换后，继续向下调整
        parent = child;          // 更新父节点下标
        child = parent * 2 + 1;  // 重新计算左孩子下标
    }
}

3. 模拟实现

3.1 常用的接口

接口	功能说明
priority_queue()	构造一个空的优先级队列（默认大顶堆）
priority_queue(InputIterator first, InputIterator last)	用迭代器区间构造优先级队列
push(const T& val)	向堆中插入一个元素，并保持堆结构
pop()	删除堆顶元素（不会返回值）
top()	返回堆顶元素（最大值或最小值，取决于比较器）
empty()	判断优先级队列是否为空
size()	返回队列中元素的个数

3.2 构造函数

在这里插入图片描述

1. 无参构造：直接构造一个空的优先级队列，默认情况下其内部维护的是一个大根堆。
2. 迭代器区间构造：利用 [begin, end) 区间内的元素来构造优先级队列。该区间是一个左闭右开的结构，即包含 begin 指向的元素但不包含 end。构造过程中，会先通过迭代器解引用，将区间内的数据依次尾插到底层容器 _con 中，直到首尾迭代器相等时结束插入。