C++详解：顶堆原理与LeetCode应用

本文档主要介绍了C++中关于顶堆问题的总结，特别是与LeetCode平台上的题目相关的内容，旨在帮助有算法基础的读者理解和解决此类问题。顶堆是一种特殊的树形数据结构，它满足父节点的值总是大于或等于其子节点的值，从而在堆顶总是存储最大（或最小）的元素。C++标准库提供了`priority_queue`这个容器，用于实现大顶堆（默认情况下），而通过提供不同的比较函数可以创建小顶堆。 **顶堆基础知识** 1. **底层原理**： - 顶堆通常基于二叉堆实现，是一棵完全二叉树，其中每个节点的值都大于或等于其子节点的值（大顶堆）或小于或等于其子节点的值（小顶堆）。 2. **C++实现**： - `priority_queue`默认使用`std::greater`进行比较，创建大顶堆。例如： ```cpp priority_queue<int> que; que.push(1); que.push(3); que.push(2); // 顶堆顺序：3, 2, 1 ``` - 若要实现小顶堆，可以传入`std::less`，或者自定义比较规则： ```cpp priority_queue<int, vector<int>, greater<int>> que; ``` - 对于自定义数据类型，如`pair`，可以使用lamda表达式或重载`<`和`>`操作符来指定排序规则： ```cpp auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.first + a.second < b.first + b.second; }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> que(cmp); ``` **题目示例：剑指Offer II 059 - 数据流的第K大数值** 这是一个简单的面试题，要求设计一个类来找到数据流中的第K大元素。这涉及到实时维护堆的性质，即每次插入新元素时，需要调整堆以保持前K个元素的大小关系。使用`priority_queue`可以方便地实现这个功能，因为它会自动处理插入和删除操作时的堆调整。 实现时，可以考虑以下步骤： 1. 初始化一个大小为K的`priority_queue`，使用`greater`作为比较函数。 2. 每次插入新元素，检查是否需要替换堆顶的第K大元素，如果是，则弹出堆顶并插入新元素。 3. 提供查询第K大元素的方法，由于堆结构保证了堆顶元素是当前第K大的，直接返回即可。 通过理解顶堆的原理和C++的`priority_queue`接口，解决这类题目将变得更加轻松。这不仅有助于提升算法技能，也为面试准备提供了实际应用场景的知识。对于C++开发者来说，掌握顶堆是提高数据结构和算法理解的关键一步。