使用小顶堆实现元素从小到达排列
#include <iostream>
#include <vector>
#include <queue>using namespace std;
priority_queue<int, vector<int>, greater<int>> topKHeap(vector<int> &nums, int k) {
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> heap;
// 将数组的前 k 个元素入堆
for (int i = 0; i < k; i++) {
heap.push(nums[i]);
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (int i = k; i < nums.size(); i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > heap.top()) {
heap.pop();
heap.push(nums[i]);
}
}
return heap;
}int main() {
vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int k = 4;
priority_queue<int, vector<int>, greater<int>> result = topKHeap(nums, k);// 输出堆中的元素
while (!result.empty()) {
cout << result.top() << " ";
result.pop();
}
cout << endl;return 0;
}