C++中的实现 (`std::priority_queue`)

std::priority_queue 默认实现的是一个大顶堆。

int: 存储的元素类型。
std::vector<int>: 实现堆所用的底层容器，vector是默认且最常用的选项。
std::greater<int>: 比较函数。默认是std::less<int>（产生大顶堆），std::greater<int>表示“小的更优先”，从而实现小顶堆。

小顶堆 (Min-Heap) 声明小顶堆需要提供额外的模板参数，来改变其默认的比较行为。

#include <queue>
#include <vector>
#include <functional> // 需要包含 greater

// 完整声明：类型, 底层容器, 比较函数
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

大顶堆 (Max-Heap) 声明方式非常简单，和普通容器一样。

#include <queue>
std::priority_queue<int> max_heap;

主要操作及其复杂度

无论是大顶堆还是小顶堆，std::priority_queue 提供的操作都是相同的，只是行为根据堆的类型有所不同。

假设 pq 是一个 priority_queue：

操作	C++ 代码	描述	时间复杂度
入堆	`pq.push(value)`	将一个新元素加入堆中，并调整结构以维持堆属性。	`O(log n)`
查看堆顶	`pq.top()`	返回堆顶元素的引用（不删除）。对于大顶堆是最大值，小顶堆是最小值。	`O(1)`
出堆	`pq.pop()`	删除堆顶元素，并调整结构以维持堆属性。注意：这个函数不返回任何值。	`O(log n)`
判空	`pq.empty()`	判断堆是否为空。	`O(1)`
获取大小	`pq.size()`	返回堆中元素的数量。	`O(1)`

典型用法：

获取并删除堆顶元素，需要两步操作：

int top_element = pq.top(); // 获取堆顶元素
pq.pop();                   // 删除堆顶元素

适用场景

堆的核心优势在于能够以 O(logn) 的高效时间复杂度插入元素，并以 O(1) 的时间复杂度随时获取到集合中的极值（最大或最小值）。最适合的场景是动态规划。

1. 大顶堆 (Max-Heap) 的适用场景

当需要频繁地找到并移除一组动态数据中的最大元素时。

任务调度系统: 在操作系统中，可以根据任务的优先级（数值越大，优先级越高）来处理任务。大顶堆的堆顶始终是优先级最高的任务，调度器每次取出堆顶任务执行即可。
数据流中位数/百分位数: 在处理动态数据流时，可以用一个大顶堆和一个小顶堆来高效地找到数据流的中位数。![[使用堆计算数据流中位数和百分位数 ]]
寻找第 K 小的元素 (Top K Smallest): 这是一个经典但有点反直觉的用法。要找到最小的K个元素，可以维护一个大小为 K 的大顶堆。遍历数据，如果堆未满，则直接插入；如果堆已满，且当前元素比堆顶元素（已找到的K个元素中的最大值）小，则弹出堆顶，插入当前元素。遍历结束后，堆中剩下的就是最小的K个元素。

2. 小顶堆 (Min-Heap) 的适用场景

当你需要频繁地找到并移除一组动态数据中的最小元素时，使用小顶堆。

Dijkstra等图论最短路径算法: 在Dijkstra算法中，需要一个数据结构来存储所有待访问的节点，并快速找到当前距离起点路径最短的节点。小顶堆（优先队列）是实现这一需求的最标准、最高效的方式。
合并 K 个有序数组/链表: 创建一个小顶堆，将 K 个列表的第一个元素全部放入堆中。每次从堆中取出最小的元素（即所有列表当前头元素中的最小值），将其加入结果列表，然后将该元素所在列表的下一个元素入堆。重复此过程，直到堆为空。
寻找第 K 大的元素 (Top K Largest): 和上面类似，要找到最大的K个元素，可以维护一个大小为 K 的小顶堆。遍历数据，如果堆未满，则直接插入；如果堆已满，且当前元素比堆顶元素（已找到的K个元素中的最小值）大，则弹出堆顶，插入当前元素。遍历结束后，堆中剩下的就是最大的K个元素。（你之前问的题目就是这个思想的应用）

C++中的实现 (std::priority_queue)

主要操作及其复杂度

适用场景

1. 大顶堆 (Max-Heap) 的适用场景

2. 小顶堆 (Min-Heap) 的适用场景

C++中的实现 (`std::priority_queue`)