按问题理解priority_queue:查找K个最近元素的解决方案

Question

我正在解决leetcode问题上的一个问题-查找K个最近元素。

这是我的IDE代码：IDE.geeksforgeks

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
std::vector<int> findClosestElements(std::vector<int>& arr, int k, int x) 
{
std::vector<int> res;
// min heap
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
std::greater<std::pair<int, int>>> pq;

std::cout << "Debug queue : n";
for (auto it : arr)
{
int closest = abs(it - x);
pq.push(std::make_pair(closest, it));        
//std::cout << closest << " : " << it << "n";

if (pq.size() > k)
{
pq.pop();     
}
}

std::cout << "nIterating queue : n";
while(!pq.empty())
{
res.push_back(pq.top().second);
std::cout << pq.top().first << " : " << pq.top().second << "n";
pq.pop();
}

std::sort(res.begin(), res.end());
return res;
}
int main()
{
std::vector<int> arr = {1,2,3,4,5};
auto res = findClosestElements(arr, 4, 3);
return 0;
}

当我迭代队列时，我看不到最小数量：0 : 3，它应该是priority_queue的顶部元素。有人能提出建议吗？

Answer 1

最大堆解决了这个问题。

vector<int> findClosestElements(vector<int>& arr, int k, int x) 
{
std::vector<int> res;
std::priority_queue<std::pair<int, int>> pq;
for (auto it : arr)
{
int closest = abs(it - x);
//std::cout << closest << " : " << it << "n";
pq.push(std::make_pair(closest, it));
if (pq.size() > k)
{
pq.pop();     
}
}
//std::cout << "nDebug queue : n";
while(!pq.empty())
{
res.push_back(pq.top().second);
//std::cout << pq.top().first << " : " << pq.top().second << "n";
pq.pop();
}
std::sort(res.begin(), res.end());
return res;
}