Use priority queue to find the K closest points to the origin

In this problem, we will find the K closest points to the origin in the 2D plane from the given N points.

We can use the standard Euclidean distance formula to calculate the distance between the origin and each given point. After that, we can store the points with distance into an array, sort the array based on distance, and take the top K points.

However, we can also use a priority queue to store 2D points based on their distance from the origin. Afterwards, we can dequeue K times from the queue.

Problem Statement− We are given N points on the two-dimensional plane. We need to find the K points closest to the origin of the plane.

Note - Treat Euclidean distance as the distance between the origin and a given point on the plane.

Example

enter

points = {{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}}, K = 4

Output

{2,1} {2,-2} {0,3} {-5,1}

Explanation − Here is the Euclidean distance from each point to the origin.

• (2, −2) −> sqrt(8)

• (−5, 1) −> sqrt(26)

• (2, 1) -> sqrt(5)

• (0, 3) −> sqrt(9)

• (6, 0) -> sqrt(36)

• (5, 5) -> sqrt(50)

• (4, 9) -> sqrt(97)

Therefore, the 4 closest points are {2,1} {2,−2} {0,3} {−5,1}.

enter

points = {{1, 2}, {2, 1}, {-2, 1}, {1, -2}} K = 2

Output

{1, 2}, {2, 1}

Explanation − The distance from all points to the origin is the same. Therefore, we can print any 2 points as output.

enter

points = {{1, 3}, {6, 7}, {1, 1}, {1, 0}} K = 4

Output

{1, 0}, {1, 1}, {1, 3}, {6, 7}

Explanation− K is equal to the given point. Therefore, we need to print all points.

method one

In this method, we will sort the array using sort() method. Additionally, we will use a comparator function to sort the points based on their distance from the origin. After that, we print the first K elements of the sorted array.

algorithm

Step 1 − Use the sort() method to sort the list and pass the distComparator() function as the third parameter.

Step 2− Define the distComparator() function to compare the distance of a given point. This function takes as parameters a pair of p and q.

Step 2.1 − Get the distance from point p to the origin and store it in dist_p.

Step 2.2 − Store the distance from point q to the origin in the dist_q variable.

Step 2.3 − If dist_p is less than dist_q, return true. Otherwise, returns false.

Step 3- Iterate through the array and print the first K points of the array.

Example

#include <bits/stdc++.h>
using namespace std;

bool distComparator(const pair<int, int> &p, const pair<int, int> &q) {
    int dist_p = p.first * p.first + p.second * p.second;
    int dist_q = q.first * q.first + q.second * q.second;
    return dist_p < dist_q;
}
vector<pair<int, int>> findKPoints(vector<pair<int, int>> points, int n, int k) {
    vector<pair<int, int>> res_points;
    sort(points.begin(), points.end(), distComparator);
    // Get the first K points
    for (int p = 0; p < k; p++)     {
        res_points.push_back({points[p].first, points[p].second});
    }
    return res_points;
}
int main() {
    int k = 4, n = 7;
    vector<pair<int, int>> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair<int, int>> res = findKPoints(points, n, k);
    cout << "The " << k << " closest points from origin are - ";
    for (int p = 0; p < k; p++) {
        cout << "{" << res[p].first << "," << res[p].second << "} ";
    }
    return 0;
}

Output

The 4 closest points from origin are - {2,1} {2,-2} {0,3} {-5,1}

Time complexity - The time complexity of sorting an array is O(NlogN).

Space Complexity - O(N) for sorting the array.

Method Two

In this method, we will use priority queue to insert points. Additionally, we will use a comparator function and a priority queue to store points based on their shortest distance from the origin.

algorithm

Step 1 − Define the ‘res_points’ list to store the K nearest points.

Step 2- Define priority queue. Here, ‘pair’ means using a priority queue to store integer pairs. ‘vector>’ means using vectors to store pairs. Additionally, we used the "cmp" function with a priority queue.

Step 3− Define the cmp() function to compare the Euclidean distance between two points and the origin.

Step 3.1 - Return a Boolean value based on the distance from point a to the origin being greater than the distance from point b to the origin.

Step 4 - Insert each element of the array into the priority queue.

Step 5− Pop the first K elements from the queue and store them in the res_points list.

Step 6− Return the res_points list of points.

Example

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> findKPoints(vector<pair<int, int>> points, int n, int k) {
    vector<pair<int, int>> res_points;
    // Custom comparator to compare points based on their distance from the origin
    auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
        return (a.first * a.first + a.second * a.second) > (b.first * b.first + b.second * b.second);
    };
    // Use the custom comparator in the priority_queue
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> p_que(cmp);
    for (int p = 0; p < n; p++) {
        // Inserting points in a queue
        p_que.push(points[p]);
    }
    // Get first K points
    while (k--) {
        auto temp = p_que.top();
        res_points.push_back(temp);
        p_que.pop();
    }
    return res_points;
}
int main() {
    int k = 4, n = 7;
    vector<pair<int, int>> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair<int, int>> res = findKPoints(points, n, k);
    cout << "The " << k << " closest points from origin are - ";
    for (int p = 0; p < k; p++) {
        cout << "{" << res[p].first << "," << res[p].second << "} ";
    }
    return 0;
}

Output

The 4 closest points from origin are - {2,1} {2,-2} {0,3} {-5,1}

Time complexity - O(N*logN) Insert N elements into the priority queue. Here, N is the total number of points.

Space Complexity - O(N) to store points in priority queue.

Priority queue uses heap data structure. Therefore, inserting and deleting elements only takes O(logN) time. Both methods require the same memory and time. However, the second method is more efficient because it uses the heap data structure.

The above is the detailed content of Use priority queue to find the K closest points to the origin. For more information, please follow other related articles on the PHP Chinese website!