https://gallery.selfboot.cn/zh/algorithms/heap

在C++里，堆（Heap）是一种重要的数据结构，它本质上是一种完全二叉树，并且满足堆属性（大顶堆中每个节点的值都大于或等于其子节点的值；小顶堆中每个节点的值都小于或等于其子节点的值）。C++标准库中的<algorithm>头文件提供了一些堆操作函数，同时堆这种数据结构能有效解决多种编程问题，以下为你详细介绍：

优先队列问题

优先队列是一种特殊的队列，其中每个元素都有一个优先级，出队操作总是返回优先级最高（或最低）的元素。堆非常适合实现优先队列，因为它可以高效地支持插入元素和删除最大（或最小）元素的操作。

应用场景示例：

• 任务调度系统：在操作系统或多线程应用程序中，任务可以被赋予不同的优先级。使用堆实现的优先队列可以快速地找到当前优先级最高的任务并执行。例如，在一个游戏服务器中，某些紧急任务（如玩家登录、断线重连）的优先级较高，需要优先处理。
• 事件驱动系统：在事件驱动的程序中，事件按照发生的时间或重要性有不同的优先级。堆可以用来管理这些事件，确保高优先级的事件先被处理。

排序问题：堆排序

堆排序是一种基于堆的排序算法，它利用堆的性质将一个无序数组转换为有序数组。堆排序的时间复杂度为 $O(n \log n)$，并且是一种原地排序算法，不需要额外的大量存储空间。

应用场景示例：

• 大规模数据排序：当需要对大量数据进行排序时，堆排序可以在相对稳定的时间复杂度内完成排序任务，尤其是在内存有限的情况下，堆排序的原地排序特性使其具有优势。

求第K大（小）元素

在一个无序数组中查找第K大（或第K小）的元素是一个常见的编程问题。使用堆可以高效地解决这个问题，时间复杂度为 $O(n \log K)$。

实现思路：

• 求第K小元素：维护一个大小为K的大顶堆。遍历数组，将元素依次插入堆中。如果堆的大小超过K，则删除堆顶元素（即当前堆中的最大值）。最终，堆顶元素就是第K小的元素。
• 求第K大元素：维护一个大小为K的小顶堆。遍历数组，将元素依次插入堆中。如果堆的大小超过K，则删除堆顶元素（即当前堆中的最小值）。最终，堆顶元素就是第K大的元素。

应用场景示例：

• 数据统计：在一个包含大量学生成绩的数组中，找出第10名学生的成绩。
• 游戏排行榜：在游戏中，根据玩家的得分找出排名第K的玩家。

图算法

在一些图算法中，堆也有广泛的应用，主要用于优化算法的时间复杂度。

应用场景示例：

• Dijkstra算法：用于求解单源最短路径问题。在Dijkstra算法中，需要不断地从未访问的节点中选择距离源节点最近的节点。使用小顶堆可以高效地完成这个选择过程，将算法的时间复杂度从 $O(V^2)$ 优化到 $O((V + E) \log V)$，其中V是图的顶点数，E是图的边数。
• Prim算法：用于求解最小生成树问题。在Prim算法中，需要不断地从未访问的节点中选择距离当前生成树最近的节点。同样，使用小顶堆可以优化这个选择过程，提高算法的效率。

数据流中的中位数

在处理数据流（即不断有新元素加入）时，需要动态地计算中位数。可以使用两个堆（一个大顶堆和一个小顶堆）来维护数据流中的元素，使得大顶堆存储较小的一半元素，小顶堆存储较大的一半元素。这样，中位数可以根据两个堆的堆顶元素快速计算出来。

应用场景示例：

• 实时数据分析：在金融领域，需要实时计算股票价格的中位数；在传感器网络中，需要实时计算传感器数据的中位数。