fork download
  1. //
  2. // main.cpp
  3. // K nearest neighbors
  4. //
  5. // Created by Himanshu on 18/08/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <algorithm>
  11. #include <math.h>
  12. using namespace std;
  13. int const N = 5;
  14.  
  15. bool cmp( const vector<float>& p,
  16. const vector<float>& q ) {
  17. return p[1] > q[1];
  18. }
  19.  
  20. void solve (int points[][2], int point[], int k) {
  21. vector< vector<float> > minHeap;
  22.  
  23. for (int i=0; i<N; i++) {
  24. float d = sqrt((pow((point[0] - points[i][0]), 2)) + (pow((point[1] - points[i][1]), 2)));
  25. float pos = i;
  26. minHeap.push_back({pos, d});
  27. push_heap(minHeap.begin(), minHeap.end(), &cmp);
  28. }
  29.  
  30. cout<<"K nearest neighbors:"<<endl;
  31. for (int i=0; i<k; i++) {
  32. vector<float> nearestPoints = minHeap.front();
  33. pop_heap(minHeap.begin(), minHeap.end(), &cmp);
  34. minHeap.pop_back();
  35. cout<<nearestPoints[0]<<" - distance: "<<nearestPoints[1]<<endl;
  36. }
  37.  
  38. }
  39.  
  40. int main () {
  41. int points[N][2] = {{1, 1}, {3, 4}, {2, 3}, {7, 8}, {2, 5}};
  42. int point[2] = {0, 0};
  43. int k = 2;
  44. solve(points, point, k);
  45. return 0;
  46. }
  47.  
Success #stdin #stdout 0.01s 5512KB
stdin
Standard input is empty
stdout
K nearest neighbors:
0 - distance: 1.41421
2 - distance: 3.60555