C++堆(优先队列)priority_queue

堆原理

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（大根堆）；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（小根堆）。
从堆的概念可知，堆是一棵完全二叉树，因此可以使用层序的规则采用顺序的方式来高效存储。
完全二叉树，我的理解：任何节点的子节点只有以下三种情况：
一，没有孩子。二，有两个孩子。三，只有左孩子。
不会出现只有右孩子，没有左孩子的情况。
cur节点如果左孩子还有后代，则cur一定有右孩子。
性质一根节点的编号1，根节点的左孩子编号2，根节点的右孩子编号3。2的孩子编号为：4,5。3的孩子编号：6,7。即节点i的孩子是：i$\times$ 2和i$\times$ 2+1。节点i的父亲节点是 i/2。即BFS序，先层次（行），再列。
由于C++的标准库有现场的类和函数，所以无需关心具体细节。

向量模拟堆

建立大根堆

我们利用make_heap建立大根堆：

const int N = 5;
			int a[N] = { 10,20,30,40,50 };
			make_heap(a, a + N);

结果为 {50, 40, 30, 10, 20} 时间复杂度O(n)

增加元素

std::push_heap 会重排容器最后一个元素，使得最大元素（对于最大堆）或最小元素（对于最小堆）位于容器的开头。时间复杂度为 O(log n)，其中 n 是堆的大小。只会影响此节点的祖先。
必须先调用make_heap，再调用push_heap，否则会除错。比如：

const int N = 6;
vector<int> a = { 10,20,30,40,50,35 };
			//make_heap(a.begin(),a.end());
			push_heap(a.begin(), a.end());

结果为：{35,20,10,40,50,30)
正确的例子：

		vector<int> a = { 10,20,30,40,50 };
			make_heap(a.begin(),a.end());
			a.push_back(35);
			push_heap(a.begin(), a.end());

结果为：{50,40,35,10,20,30}

删除元素

std::pop_heap 将堆中的最大元素（对于最大堆）或最小元素（对于最小堆）移动到容器的末尾，并保持剩余元素的堆属性。并不会直接移除元素，而是将最大或最小元素移到容器的末尾。需要手动调用 pop_back() 来移除该元素。std::pop_heap 之后，容器的前 n-1 个元素仍然是一个有效的堆。时间复杂度为 O(log n)。用堆的最后一个元素替换根，确保跟换的节点大于两个孩子，否则和较大的孩子互换。

vector<int> a = { 10,20,30,40,50 };
			make_heap(a.begin(),a.end());
			pop_heap(a.begin(), a.end());
			a.pop_back();

结果为：{40,20,30,10}

建立小根堆

vector<int> a = { 10,20,30,50,40 };
			make_heap(a.begin(),a.end(),greater<>());

结果不变。

C++堆(优先队列)。

建立堆

	vector<int> a = { 10,20,30,50,40 };
			priority_queue<int> maxHeap(a.begin(), a.end());
			priority_queue<int, vector<int>, greater<>> minHeap(a.begin(), a.end());

大根堆为：{50,40,30,20,10} 小根堆和a同。

其它函数

获取堆顶元素
auto cur = maxHeap.top();
弹出堆顶元素
maxHeap.pop();
增加元素
maxHeap.push(3);

解题技巧

双堆（对顶堆)

总共有n个数，大根堆记录较小的n/2个数，小根堆记录余下的数。方便求中位数。

懒删除堆

记录堆中要删除的元素，如果堆顶的元素是要删除的元素，则删除。解决：堆无法删除非堆顶元素的问题。

反悔堆

‌反悔堆‌是一种特殊的贪心算法，它允许在贪心选择后进行反悔，从而调整之前的决策。反悔堆通过维护一个堆（最大堆或最小堆）来快速找到当前最优解，并在必要时进行反悔操作，以获得全局最优解。
‌课程表问题‌：选择最优的课程组合，避免时间冲突。
‌最低加油次数问题‌：在加油站点选择最优路径，确保到达目的地。
‌工作调度问题‌：在截止日期前完成收益最大的工作，避免时间冲突。

题解

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。