একটি অনসর্টেড (unsorted) অ্যারে A দেওয়া থাকলে, দুটি মান X এবং k দেওয়া থাকলে, অ্যারেতে থেকে X-এর নিকটতম k সংখ্যক উপাদান বের করতে হবে। যদি X অ্যারেতে থাকে, তবে আউটপুটে দেখানো হবে না। A = [48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56], X = 35, k = 4 হলে আউটপুট: 30, 39, 42, 45।
সমাধান: হিপ (heap) ডেটা স্ট্রাকচার ব্যবহার করা হবে। ধাপগুলো:
প্রথম k উপাদানের পার্থক্য (difference) দিয়ে একটি ম্যাক্স-হিপ (max-heap) তৈরি করা
k+1 তম উপাদান থেকে প্রতিটি উপাদানের জন্য:
বর্তমান উপাদান এবং X-এর পার্থক্য বের করা
যদি পার্থক্য হিপের রুট (root) থেকে বড় হয়, তবে বর্তমান উপাদান উপেক্ষা করা
অন্যথায় রুট সরিয়ে বর্তমান উপাদান হিপে ঢুকানো
শেষে হিপে kটি নিকটতম উপাদান পাওয়া যাবে
উদাহরণ
#include <iostream> #include<queue> using namespace std; void findKClosestNumbers(int arr[], int n, int x, int k) { priority_queue > priorityQ; for (int i = 0; i < k; i++) priorityQ.push({ abs(arr[i] - x), i }); for (int i = k; i < n; i++) { int diff = abs(arr[i] - x); if (diff > priorityQ.top().first) continue; priorityQ.pop(); priorityQ.push({ diff, i }); } while (priorityQ.empty() == false) { cout << arr[priorityQ.top().second] << " "; priorityQ.pop(); } } int main() { int arr[] = {48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56}; int x = 35, k = 5; int n = sizeof(arr) / sizeof(arr[0]); findKClosestNumbers(arr, n, x, k); } আউটপুট
45 42 30 39 35
