215.数组中的第K个最大元素（堆排序）

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解法

priority_queue<int, vector, greater> pq这个是自定义的数据结构吗？

priority_queue<int, vector<int>, greater<int>> pq 并不是自定义的数据结构，而是 C++ 标准库中的优先队列（priority_queue）的一种使用方式。这里的 greater<int> 表示优先队列是最小堆（min-heap），也就是说，优先队列中最小的元素会被优先访问。

• int 是存储在优先队列中的元素类型。
• vector<int> 是底层容器，存储元素的实际位置。
• greater<int> 是一个比较器，用于决定元素的优先级。

如果你不使用 greater<int>，默认情况下，priority_queue 是最大堆（max-heap），即最大元素会被优先访问。
类似unordered_map，是c++自带的

pq.emplace(num);

pq.emplace(num); 是用于向优先队列 pq 中添加元素的一个方法。与 push(num) 类似，emplace 方法会直接在优先队列的底层容器中构造元素。它的好处在于可以避免不必要的拷贝，提高性能，特别是在处理复杂对象时。

在这种情况下，如果 num 是一个整数，emplace(num) 和 push(num) 的效果是相同的。优先队列会根据之前设置的比较器（这里是 greater<int>）自动调整其结构，以保持堆的性质。

优先队列中插入元素会自动把最小的放在堆顶吗？

是的，当你向优先队列中插入元素时，最小的元素会自动被放在堆顶。这是因为你使用了 greater 作为比较器，这样优先队列会维持最小堆的特性，即每次插入后，堆顶元素始终是当前最小的元素。

原文地址：https://blog.csdn.net/qq_43920838/article/details/143200321

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！