在CSP - J备考的强化阶段（第3 - 4个月），STL容器的深入学习是非常重要的部分，其中优先队列的自定义更是重中之重，尤其是在解决Dijkstra算法处理带权图最短路径问题中的应用。
一、优先队列自定义知识点内容
1. 结构体重载operator <实现大根堆/小根堆
- 大根堆：
- 大根堆的特点是堆顶元素是整个堆中的最大值。对于一个结构体类型的数据，如果要构建大根堆，需要重载小于运算符（operator <）。例如，假设有一个结构体struct Node { int value; }，要构建大根堆，在重载小于运算符时，应该让值较大的元素在比较时被认为“小”。代码可能是bool operator < (const Node& other) const { return value > other.value; }。这样在优先队列中，按照默认的大根堆规则（比较小的元素在堆顶），实际上是值大的元素会处于堆顶。
- 小根堆：
- 小根堆则相反，堆顶元素是最小值。对于上述结构体，如果要构建小根堆，重载小于运算符可能是bool operator < (const Node& other) const { return value < other.value; }。这样在优先队列中就会按照小根堆的规则运行。
2. 学习方法
- 理解堆的概念：首先要深入理解大根堆和小根堆的基本概念，可以通过简单的数组模拟堆的构建过程来加深认识。比如手动构建一个包含几个整数的小根堆，观察元素的排列顺序。
- 多做练习题：针对结构体重载小于运算符的题目进行大量练习。从简单的单属性结构体开始，逐渐过渡到包含多个属性的结构体。例如，先练习只根据一个整数属性构建堆，再练习根据结构体中的多个属性（如坐标结构体中的x和y坐标综合比较）来构建堆。
二、Dijkstra算法中使用优先队列优化的具体步骤（处理带权图最短路径问题）
1. 步骤内容
- 初始化：
- 首先要初始化距离数组dis[]，将起始点的距离设为0，其他点的距离设为无穷大（可以用一个很大的数表示，如INT_MAX）。同时创建一个优先队列，将起始点加入优先队列。
- 循环处理：
- 当优先队列不为空时，取出堆顶元素（这个元素是当前距离起始点最近的未确定最短路径的点）。然后遍历这个点的所有邻接点。对于每个邻接点，如果通过当前点到达邻接点的距离比之前记录的距离短，就更新邻接点的距离，并将邻接点加入优先队列（如果邻接点已经在队列中，由于距离更新可能会改变其在队列中的位置）。
- 结束条件：
- 当优先队列为空时，整个算法结束，此时dis[]数组中存储的就是从起始点到各个点的最短距离。
2. 学习方法
- 手动推导：对于简单的图（如只有几个节点和边的图），手动按照Dijkstra算法的步骤进行推导，观察距离数组和优先队列的变化情况。
- 对比无优化的Dijkstra算法：对比使用优先队列优化前后的Dijkstra算法在时间复杂度、代码简洁性等方面的差异，从而更好地理解优化的意义。
总之，在CSP - J备考的这个阶段，要熟练掌握优先队列自定义的知识点以及它在Dijkstra算法中的应用。通过不断地练习相关题目，加深对概念的理解，提高解题能力，为顺利通过CSP - J考试打下坚实的基础。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
