当前位置：首页 > news >正文

【数据结构】堆和priority_queue

news 来源：原创 2025/8/29 10:39:52

堆的定义

堆是什么？实际上堆是一种特殊的（受限制的）完全二叉树，它在完全二叉树的基础上要求每一个节点都要大于等于或者小于等于它的子树的所有节点。这个大于小于体现在节点的值或者权重。

如图所示：
根节点大于等于子树中所有节点的堆叫做大顶堆（大根堆）
根节点小于等于子树中所有节点的堆叫做小顶堆（小根堆）
在这里插入图片描述

堆的存储

堆属于完全二叉树，因此使用二叉树的顺序存储结构来存储堆是最优的。

堆的核心操作（默认以大根堆为标准）

向上调整算法

一般使用背景：

在堆的最后面插入一个元素之后，要将这个节点调整到正确的位置。

流程：

将该节点的值直接与父节点相比较，如果比父节点大就要与父节点交换。重复此步骤一直到比父节点小或者已经换到了根节点，就完成了向上调整，此时这个新来的节点就已经被调整到了正确的位置。

注意事项：

向上调整算法就是子节点要跟父节点换，一个子节点的父节点只有一个，所以直接交换即可。

代码实现

//向上调整 
void up(int child) //传入要调整的节点的下标（下标具有唯一性，堆中允许节点的值相同） 
{int parent = child / 2;while(parent >= 1 && heap[child] > heap[parent]) // 这里必须是parent >= 1 ，不能是parent > 1 。 parent > 1时，如果该节点是最大的，那么只能被调整到堆顶的子节点的位置。{swap(heap[child],heap[parent]);//被换掉的那个元素就不管了，它已经在正确的位置上了，现在我们要更新child节点 ，然后再由公式得出parent节点 child = parent;parent = child / 2;}
}

向下调整算法

一般使用背景：

先了解堆pop()的原理是什么？
堆pop()删除堆顶元素的逻辑是将目前的堆顶元素与堆的最后一个元素交换，然后将堆的大小-1，这样就访问不到最后的那个元素了（原来的堆顶元素）。

在删除堆顶元素之后，本身在最后位置的元素来到了堆顶（根部），这时候的堆只有左右子树是合法的，整体是不合法的，所以就要进行向下调整算法，将目前的堆顶元素调整到正确的位置。

流程：

将要向下调整的节点的值与两个子节点中最大的那个值相比较，如果该节点的值比子节点的最大值要小，就交换。重复此步骤，直到该节点的值比子节点的最大值大或者已经被换到了叶子节点，那么此时该节点就被调整到了正确的位置。

注意事项：

向下调整算法是父节点要跟子节点换，一个父节点最多有两个子节点，所以我们要找出最大的那个子节点作比较。

代码实现

//向下调整 
void down(int parent)
{int child = parent * 2; //先默认指向左节点 思考：child是两倍的parent得到的，这个时候有没有可能超出了n呢？所以要先判断child是否存在 while(child <= n) //孩子存在才有下文   {if(child + 1 <=n && heap[child] < heap[child + 1]) child++;if(heap[parent] >= heap[child]) return; //heap[parent] >= heap[child]比heap[parent] > heap[child]少走一步，但都是正确的swap(heap[parent],heap[child]);parent = child;child = parent * 2;}
}

堆的模拟实现

//默认建大根堆 
#include <iostream>
using namespace std;const int N = 1e6 + 10;
int n,heap[N]; //n用来记录heap存放的有效元素个数，heap用来存储堆的数据，父子关系是靠公式计算得来（堆是完全二叉树） //向上调整 
void up(int child) 
{int parent = child / 2;while(parent >= 1 && heap[child] > heap[parent]){swap(heap[child],heap[parent]);child = parent;parent = child / 2;}
}//向下调整
void down(int parent)
{int child = parent * 2;  while(child < n)   {if(heap[child] < heap[child + 1]) child++;if(heap[parent] >= heap[child]) return;swap(heap[parent],heap[child]);parent = child;child = parent * 2;}
}void push(int x)
{heap[++n] = x; //最刚开始n=0，存入第一个元素的时候++n，是在1的位置存入，0的位置没有任何元素 up(n);
}void pop()
{swap(heap[1],heap[n]);n--;down(1); //要搞清楚堆的根存放在哪里
}int size()
{return n;
}int top() 
{return heap[1];
}int main() 
{int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};for(int i=0;i<sizeof(a)/sizeof(int);i++){push(a[i]);}while(size()){cout << top() << " ";pop();}return 0;
}

运行结果：
在这里插入图片描述

注意：这个top实际上是有bug的，就是在没有元素的时候是不能调用这个接口的，这样的条件检查我们不在函数内实现，而是在调用前进行检查。同样的，有一个在做题时遇到的小细节值得注意，也是关于栈中top接口的调用。

题外话

P4387 【深基15.习9】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 $n(n\le100000)$ 。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据，不超过 $5$ 组。

输入格式

第一行一个整数 $q$ ，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

输入输出样例 #1

输入 #1

输出 #1

Yes
No

这是我当时的代码：

#include<iostream>
#include<stack>
using namespace std;const int N = 1e5 + 10; 
int in[N],out[N];int main()
{	int q;cin >> q;while(q--){stack<int> st; //栈必须放在循环内，要不然每次重新接受数据前要清空栈元素 int n;cin >> n;for(int i=1;i<=n;i++) cin >> in[i];	for(int i=1;i<=n;i++) cin >> out[i];int t = 1; //t指针指向out的第一个元素 for(int i=1;i<=n;i++){st.push(in[i]);while(t <= n && st.top() == out[t] && st.size()) //t <= n不能丢，要不然两个序列完全匹配的时候t就会加到n+1，那样就死循环了 {st.pop(); t++;}}if(st.size()) cout << "No" << endl;else cout << "Yes" << endl;}return 0;
}

看起来似乎没有问题，但是当时一直报错 runtime error ，我也不知道错在哪，到最后才注意到， while() 语句中用 && 连接的连续条件判断是从左到右执行的，在 st.top() 调用之前应该确保栈不为空，所以 st.size() 的检查一定要放在 st.top() == out[t] 的前面。

使用 &&（逻辑与）连接的多个条件判断是有顺序的，这与 C++ 的短路求值（short-circuit evaluation）机制有关。
C++ 在使用 && 连接多个条件时，会从左到右依次评估每个条件表达式。如果左侧的条件已经为 false，则右侧的条件表达式不会被求值，因为无论右侧条件是什么，整个 && 表达式的结果都会是 false。这种行为被称为短路求值。

int a = 0;
int b = 5;while (a != 0 && b / a > 1) {// do something
}

在这个例子中，a != 0 会被首先评估。如果 a 为 0，b / a > 1 这一部分的表达式将不会被求值，避免了除以零的错误。&& 运算符是有顺序的，并且遵循短路求值规则。左侧条件为 false 时，右侧条件不会被求值。

priority_queue

普通的队列是先进先出(FIFO)的结构，priority_queue是一种基于堆实现的优先级队列，priority_queue中的元素都是有优先级的，它在插入元素时，即使是在队尾插入，也会根据优先级调整到相对应的位置，优先级越高越靠近队头的位置。同样删除元素也是删除优先级最高的元素。

priority_queue 的模板定义

priority_queue 的模板定义如下：

template <class T, class Container = std::vector<T>, class Compare = std::less<T>>
class priority_queue;

T：存储的数据类型（如 int）。
Container：底层存储结构，默认是 std::vector（但也可以用 std::deque 等）。
Compare：比较函数对象，决定优先级顺序，默认是 std::less（最大堆）。
默认是大根堆，std::less 表示大的值优先，std::greater 表示小的值优先。
就是这个比较反人性，跟常规的比较函数是反过来的。

简单创建priority_queue（这样创建默认是大根堆）

#include<iostream>
#include<queue>using namespace std;int main()
{priority_queue<int> heap; //默认大根堆int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};for(int i=0;i<sizeof(a)/sizeof(int);i++){heap.push(a[i]);}while(heap.size()){cout << heap.top() << " ";heap.pop();}return 0;
}

运行结果：
在这里插入图片描述

创建基本数据类型的优先级队列（可将int替换成其他基本数据类型）

#include<iostream>
#include<queue>using namespace std;int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};void test1()
{//priority_queue<数据类型，实现结构，排序方式>//大根堆 priority_queue<int,vector<int>,less<int>> heap1;//小根堆 priority_queue<int,vector<int>,greater<int>> heap2;for(int i=0;i<10;i++){heap1.push(a[i]); } while(heap1.size()){cout << heap1.top() << " ";heap1.pop(); }cout << endl; for(int i=0;i<10;i++){heap2.push(a[i]); } while(!heap2.empty()){cout << heap2.top() << " ";heap2.pop(); }
} int main()
{test1();return 0;
}

运行结果：
在这里插入图片描述

创建结构体数据类型的优先级队列

当 priority_queue 存储的是结构体而不是基本类型，C++ 不会默认知道如何比较结构体的优先级。因此我们必须提供比较方式，否则会导致编译错误。

方式一：重载运算符operator<

#include <iostream>
#include <queue>
#include <vector>struct Person {std::string name;int age;// 重载 < 运算符，默认用于 std::priority_queuebool operator<(const Person& other) const {return age < other.age; // 年龄大的优先级更高（最大堆）}
};int main() {std::priority_queue<Person> pq;pq.push({"Alice", 25});pq.push({"Bob", 30});pq.push({"Charlie", 20});while (!pq.empty()) {std::cout << pq.top().name << " " << pq.top().age << std::endl;pq.pop();}return 0;
}

运行结果：
在这里插入图片描述

方式二：使用自定义比较函数

可以提供一个自定义比较函数作为 priority_queue 的第三个模板参数。
这时 priority_queue 的第三个参数的定义：class Compare = std::less ，要求传入的是一个类型，而不是普通函数，所以这个比较函数必须是一个可调用对象。那么自定义比较函数不能是普通函数，而一般需要使用结构体（仿函数）或 lambda 表达式。

#include <iostream>
#include <queue>
#include <vector>struct Person {std::string name;int age;
};// 自定义比较仿函数
struct ComparePerson {bool operator()(const Person& a, const Person& b) {return a.age > b.age; // 年龄小的优先级更高（最小堆）}
};int main() {std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;pq.push({"Alice", 25});pq.push({"Bob", 30});pq.push({"Charlie", 20});while (!pq.empty()) {std::cout << pq.top().name << " " << pq.top().age << std::endl;pq.pop();}return 0;
}

方式三：使用 Lambda 表达式

C++11 之后，可以用 lambda 来替代仿函数。
如果不想写额外的比较结构体，可以直接使用 Lambda 作为比较函数：

#include <iostream>
#include <queue>
#include <vector>struct Person {std::string name;int age;
};int main() {// Lambda 比较函数auto cmp = [](const Person& a, const Person& b) {return a.age > b.age; // 年龄小的优先级更高（最小堆）};std::priority_queue<Person, std::vector<Person>, decltype(cmp)> pq(cmp);//decltype(cmp) 自动推导 Lambda 类型pq.push({"Alice", 25});pq.push({"Bob", 30});pq.push({"Charlie", 20});while (!pq.empty()) {std::cout << pq.top().name << " " << pq.top().age << std::endl;pq.pop();}return 0;
}

堆的定义

堆的存储

堆的核心操作（默认以大根堆为标准）

向上调整算法

一般使用背景：

流程：

注意事项：

代码实现

向下调整算法

一般使用背景：

流程：

注意事项：

代码实现

堆的模拟实现

题外话

P4387 【深基15.习9】验证栈序列

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

priority_queue

priority_queue 的模板定义

简单创建priority_queue（这样创建默认是大根堆）

创建基本数据类型的优先级队列（可将int替换成其他基本数据类型）

创建结构体数据类型的优先级队列

方式一：重载运算符operator<

方式二：使用自定义比较函数

方式三：使用 Lambda 表达式

相关文章：