C++堆(优先队列)priority_queue详解

C++堆(优先队列)priority_queue详解

堆是C++标准库中非常重要的数据结构之一，它在算法和数据处理中有着广泛的应用。本文将详细介绍堆的基本原理、使用方法以及在实际算法题目中的应用技巧，帮助读者全面掌握这一重要数据结构。

堆原理

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（大根堆）；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（小根堆）。

从堆的概念可知，堆是一棵完全二叉树，因此可以使用层序的规则采用顺序的方式来高效存储。

完全二叉树，我的理解：任何节点的子节点只有以下三种情况：
一，没有孩子。二，有两个孩子。三，只有左孩子。
不会出现只有右孩子，没有左孩子的情况。
cur节点如果左孩子还有后代，则cur一定有右孩子。

性质一 根节点的编号1，根节点的左孩子编号2，根节点的右孩子编号3。2的孩子编号为：4,5。3的孩子编号：6,7。即节点i的孩子是：i × 2和i × 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.pop();
增加元素
maxHeap.push(3);

解题技巧

双堆（对顶堆)

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

懒删除堆

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

反悔堆

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

题解