C++堆(优先队列)priority

C++堆(优先队列)priority_queue

2025-02-17 09:54:14 阅读次数：12

堆原理

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（大根堆）；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（小根堆）。
从堆的概念可知，堆是一棵完全二叉树，因此可以使用层序的规则采用顺序的方式来高效存储。
完全二叉树，我的理解：任何节点的子节点只有以下三种情况：
一，没有孩子。二，有两个孩子。三，只有左孩子。
不会出现只有右孩子，没有左孩子的情况。
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)
C++堆(优先队列)priority_queue

增加元素

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

结果不变。