# K Closest points - Priority Queue / Heap / Top K

Please add framework .net version 6.0, so that I can execute the Priority Queue related stuff. Thanks.

Thank you. We will consider .net 6.0

Hello,
My solution only uses heapify on the original array then uses heappop k times appending the value to the return list.
I am not using any geometry formula like it is stated in the solution, but my solution is still successfulâ€¦ Is my solution correct? Or are the tests incorrect?

Thanks,
Dylan

Iâ€™m a little confused by this alternative solution with the max heap. It says â€śIf the new point has a smaller distance, then we pop the root of the max heap and push the new point in.â€ť But in the code, it says:
`if dist(pt) > max_heap[0][0]:`
Should it be less than instead of greater than?

Wouldnâ€™t using heapify on the list and returning k items in the list result in a better time complexity?

The python docs say heapify is a linear time operation.
https://docs.python.org/3/library/heapq.html#heapq.heapify

Note: time complexity of the alternate solution is KLog(N)

â€śis sqrt((x1 - x2)^2, (y1 - y2)^2). For distance to origin, (x2, y2) is (0, 0) so distance becomes sqrt(x1^2, y1^2).â€ť
the formula is sqrt((x1-x2)^2 + (y1-y2)^2)

This is because the signs are inverted while adding to the heap, so comparison sign also changes

@Tulip in a heap, only the root is guaranteed to be â€śin sorted orderâ€ť - that is, you know for sure that the root / first element is the MIN value, but the immediately following elements are not necessarily â€śthe next minimum valuesâ€ť of the list. You need to heappop the list to re-heapify / sort the list to get the next minimum value.

It would work if you used absolute values - the test cases donâ€™t have negative coordinates, but theyâ€™re possible.

How on earth am I supposed to memory imports for PriorityQueue, Comparator, implementations for the Comparator Interface and all? This is really tough to be sincere for an old man like me.

they use the â€śpythonifiedâ€ť notation

yes, but still using heapify to create the heap is more efficient, O(n), than pushing all n elements to the heap using heappush, O(nlogn)

It comes with time. The more you use it the less of a mystery it becomes! And youâ€™ll remember the imports easier.

Change the first test case a little. Instead of the point (1, 1) change it to (1, 5). The test case will fail and then you can implement the actual correct solution (I did the same thing).

Easy to understand

``````using namespace std;

// <distance, point>
using PointPair = pair<int, vector<int>>;

struct Compare{
bool operator()(PointPair & a, PointPair & b) {
return a.first > b.first;
}
};

int distance(vector<int> point) {
return ((point[0] * point[0]) + (point[1] * point[1]));
}

std::vector<std::vector<int>> k_closest_points(std::vector<std::vector<int>> points, int k) {
priority_queue<PointPair, vector<PointPair>, Compare> pq;

for(auto point: points) {
pq.push(make_pair(distance(point), point));
}
vector<vector<int>> res;
while(k--){
res.push_back(pq.top().second);
pq.pop();
}
return res;
}
``````

Would it be cheating if I did the 1-liner in python?

return heapq.nsmallest(k, points)

Should be Nlog(K) actually since we keep K elements in the heap but we go through the list of coordinate N times.

Still waiting on .NET v 6.0.

1 Like