Heap: K closest number

Problem Statement:

You are given an array and a value k and x.
You need to find the k closest elements to x in arr[]

Example

arr[] = { 5, 6, 7, 8, 9}
k = 3
x = 7

The closest values of x are 6, 7, 8

Solution

Subtract x with all the elements of the array

5, 6, 7, 8, 9
7  7  7  7  7
--------------
2  1  0  1  2

You can consider the smallest difference, you will get the solution.

So for this we need to have a pair of the element and the differece.

Now we will have to take max_heap, because we need to get the min values and remove the max elements.

In max_heap, smallest element at the lowest and we pop the greater element. For us we need the closest that is useful. and pop the max difference that is useless.

We will sort based on the first element of pair<int, int>. i.e the difference value. So we used max_heap, the min value will be at the bottom, and we will be popping the max values.

Final elements inside the stack/heap will give the result.

Here pair<int, int> = pair <the difference, element_value>

Pass 1: 5

Stack = {2, 5}

Pass 2: 6

Stack = {1, 6}, {2, 5}

Pass 3: 7

Stack = {0, 7}, {1, 6}, {2, 5}

Pass 4: 8

Stack = {0, 7}, {1, 6}, {1, 8}, {2, 5}
As the heap size is 3, we need to pop the top most pair {2, 5}.

Stack after popping = {0, 7}, {1, 6}, {1, 8}

Pass 5: 9

Stack = {0, 7}, {1, 6}, {1, 8}, {2, 9}

Again pop the top most pair. Remaining elements are the result.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

void print_k_closest(vector<int>& arr, int x, int k)
{
    int n = arr.size();
    // Make a max heap of difference with
    // first k elements.
    priority_queue<pair<int, int> > max_heap;

    //push the first k elements
    for (int i = 0; i < k; i++)
        max_heap.push({ abs(arr[i] - x), i });
 
    // process for remaining elements
    for (int i = k; i < n; i++) 
    {
 
        int diff = abs(arr[i] - x);
        
        //if the diff is more than the top, then skip it
        if (diff > max_heap.top().first)
            continue;
 
        //else pop the top element and insert the current pair
        max_heap.pop();
        max_heap.push({ diff, i });
    }
 
    // print contents of heap.
    cout<<"Solution = ";
    while (max_heap.empty() == false) 
    {
        cout << arr[max_heap.top().second] << " ";
        max_heap.pop();
    }
    cout<<endl;
}

int main()
{
    vector<int> arr = { 5, 6, 7, 8, 9 };
    int k = 3;
    int x = 7; 
    print_k_closest(arr, x, k);
    return 0;
}

Output:

Solution = 8 6 7