浙江英文网站建设台州市城乡建设规划局网站

堆排序

• 前言
  • 面试中著名的 TopK 排序；
  • 常见的解法有冒泡排序、堆排序；
  • 更深入的思路可以参考：拜托，面试别再问我TopK了！！！
  • 使用了堆排序的算法，关于堆可以参考：堆数据结构的C++实现
• 思路：
  • 使用一个 size = k 小顶堆，之后的元素如果大于堆顶，则将堆顶 pop 后，将此元素入堆，遍历完成后，堆顶即为 TopK 元素；
  • 使用了 stl 的优先队列数据结构，默认是大顶堆，小顶堆的构造为：

    • std::priority_queue<int, std::vector<int>, std::greater<int>>

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {std::priority_queue<int, std::vector<int>, std::greater<int>> pq;int size = nums.size();for (int i = 0; i < size; ++i) {if (i < k) {pq.push(nums[i]);} else {if (nums[i] > pq.top()) {pq.pop();pq.push(nums[i]);}}}return pq.top();}
};