mercredi 21 juillet 2021

Understanding priority_queue by problem : Find K Closest Elements Solution

I was solving one problem on leetcode problem - Find K Closest Elements.

Here is my IDE code : ide.geeksforgeeks

#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;
}

While I was iterating the queue, I can not see the minimum number : 0 : 3 which should be the top element of priority_queue. Can anyone please suggest?

Aucun commentaire:

Enregistrer un commentaire