Posted on by Kalkicode
Code Heap

# Find k closest numbers in an unsorted array

In various applications, it's often necessary to find the K closest numbers to a given value X in an unsorted array. This problem requires sorting the array and then selecting the K closest elements to the target value. In this article, we'll explore a C program that solves this problem efficiently using a heap-based approach.

## Problem Statement and Description

Given an unsorted array and two integers, X and K, the task is to find and display the K closest elements to the value X in the array. The array is unsorted, so we need to first sort it before identifying the K closest elements. For example, consider the array `arr = {4, 2, 1, 10, 15, 17, 20, 14, 5}`, X = 9, and K = 4. We want to find the 4 closest elements to 9 in the given array.

## Idea to Solve the Problem

To solve this problem, we'll use a heap-based approach. We'll implement a min-heap that allows us to efficiently retrieve the K smallest (closest) elements from the array after sorting it. The steps include:

1. Sort the array using a heap sort.
2. Find the location of the first element in the array that is less than or equal to X.
3. Initialize two pointers, one pointing to the found location and another to the element just before it.
4. Compare the absolute differences of the current two pointers' elements with X. Select the element with the smaller difference and move the respective pointer accordingly.
5. Repeat this process K times to find the K closest elements.

## Pseudocode

``````function swap(arr, first, second)
// Swaps two elements in the array

function compare(arr, left, right, root, size)
// Compares elements and returns the index of the smaller element

function heap(arr, size, root)
// Creates a min-heap

function sort_element(arr, size)
// Sorts the array using heap sort

function difference(arr, i, j, x)
// Compares the absolute differences between arr[i] and arr[j] with x

function closest_k(arr, size, x, k)
sort_element(arr, size)
location = find_location(arr, size, x)
back = location - 1
i = 0
while i < k
temp = difference(arr, back, location, x)
print arr[temp]
if temp == location
location++
else
back--
i++

function main()
arr = {4, 2, 1, 10, 15, 17, 20, 14, 5}
size = sizeof(arr) / sizeof(arr)
x = 9, k = 4
closest_k(arr, size, x, k)``````

## Algorithm Explanation

1. The `swap` function swaps two elements in the array.
2. The `compare` function compares the elements at indices `left` and `right` with the element at index `root` and returns the index of the smaller element.
3. The `heap` function creates a min-heap by comparing elements and swapping them if needed.
4. The `sort_element` function sorts the array using heap sort by repeatedly calling the `heap` function.
5. The `difference` function calculates the absolute differences between two elements and the value `x`, then returns the index of the element with the smaller difference.
6. The `closest_k` function sorts the array, finds the initial location, and iterates to find the K closest elements. It prints each element found.
7. In the `main` function, the given array is initialized, and the `closest_k` function is called to find and display the K closest elements to the given value X.

## Code Solution

``````//C Program
//Find k closest numbers in an unsorted array
#include <stdio.h>

//Swap two element in array
void swap(int arr[],int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}

int compare(int arr[],int left,int right,int root,int size)
{
int location = -1;

if(left < size &&  arr[left] > arr[root] )
{

if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
void heap(int arr[],int size,int root)
{
int left  = 2*root+1;
int right = 2*root+2;

int next_in = compare(arr, left, right, root, size);

if(next_in != -1)
{
heap(arr,size,next_in);
}
}
void print_array(int arr[],int size)
{
printf("\n");
for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
}
void sort_element(int arr[],int size)
{

for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
int difference(int arr[],int i,int j,int x)
{
int first = arr[i]-x;
int second = arr[j]-x;

if(first<0)
{
first=-first;
}
if(second<0)
{
second=-second;
}
if(first > second)
{
return j;
}
else
{
return i;
}
}
//Display k closest elements of value x in given array
void closest_k(int arr[],int size,int x,int k)
{

if(k > size)
{
//invalid possibility
return;
}
//first sort array element
sort_element(arr,size);

int location=-1,back=0,i=0,temp=0;

//Find First element which is less than or equal to given value x
for (i = 0; i < size; ++i)
{
if(x <= arr[i])
{
location  = i;
break;
}
}

if(location==-1)
{
if(x > arr[size-1])
{
//point to last element
location = size-1;
}
else
{
//point to first element
location = 0;
}
}
back=location-1;
printf(" Nearest %d elements of value %d is :\n",k,x );

i = 0;
while(i < k)
{
if(location <size && back>-1)
{
temp = difference(arr,back,location,x);

printf(" %d ",arr[temp] );

if(temp == location)
{
location++;
}
else
{
back--;
}

}
else if(location < size)
{
printf(" %d ",arr[location] );
location++;

}
else if(back>0)
{
printf(" %d",arr[back] );
back--;

}
i++;
}
printf("\n");
}

int main()
{
//Define Collection of array elements
int arr[] = {4, 2, 1, 10, 15, 17, 20 , 14, 5};

//Get the size of array
int size = sizeof(arr)/sizeof(arr);

// x is value
// k is size of closest element
int x = 9, k = 4;

closest_k(arr,size,x,k);

return 0;
}```
```

#### Output

`````` Nearest 4 elements of value 9 is :
10  5  4  14``````
``````#include<iostream>

using namespace std;

/*
C++ Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
public:

//Swap two element in array
void swap(int arr[], int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
int compare(int arr[], int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this->swap(arr, right, root);
location = right;
} else {
this->swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this->swap(arr, right, root);
location = right;
}
return location;
}
void heap(int arr[], int size, int root) {
int left = 2 *root + 1;
int right = 2 *root + 2;
int next_in = this->compare(arr, left, right, root, size);
if (next_in != -1) {
this->heap(arr, size, next_in);
}
}
void print_array(int arr[], int size) {
cout << "\n";
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
}
void sort_element(int arr[], int size) {
for (int i = (size / 2) - 1; i >= 0; i--) {
this->heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--) {
this->swap(arr, 0, i);
this->heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
int difference(int arr[], int i, int j, int x) {
int first = arr[i] - x;
int second = arr[j] - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
void closest_k(int arr[], int size, int x, int k) {
if (k > size) {
//invalid possibility

return;
}
//first sort array element
this->sort_element(arr, size);
int location = -1, back = 0, i = 0, temp = 0;
//Find First element which is less than or equal to given value x

for (i = 0; i < size; ++i) {
if (x <= arr[i]) {
location = i;
break;
}
}
if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
cout << " Nearest " << k << " elements of value " << x << " is :\n";
while (i < k) {
if (location < size && back > -1) {
temp = this->difference(arr, back, location, x);
cout << " " << arr[temp];
if (temp == location) {
location++;
} else {
back--;
}
i++;
} else
if (location < size) {
cout << " " << arr[location];
location++;
i++;
} else
if (back > 0) {
cout << " " << arr[location];
back--;
i++;
}
}
cout << "\n";
}
};
int main() {
MyHeap obj = MyHeap();
int arr[] = {
4,
2,
1,
10,
15,
17,
20,
14,
5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr);
// x is value
// k is size of closest element
int x = 9, k = 4;
obj.closest_k(arr, size, x, k);
return 0;
}```
```

#### Output

`````` Nearest 4 elements of value 9 is :
10 5 4 14``````
``````/*
Java Program
Find k closest numbers in an unsorted array
*/
public class MyHeap {

//Swap two element in array
public void swap(int []arr,int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}

public int compare(int []arr,int left,int right,int root,int size)
{
int location = -1;

if(left < size &&  arr[left] > arr[root] )
{

if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
public void heap(int []arr,int size,int root)
{
int left  = 2*root+1;
int right = 2*root+2;

int next_in = compare(arr, left, right, root, size);

if(next_in != -1)
{
heap(arr,size,next_in);
}
}
public void print_array(int []arr,int size)
{
System.out.print("\n");
for(int i = 0; i < size; i++)
{
System.out.print("  "+arr[i] );
}
}
public void sort_element(int []arr,int size)
{

for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
public int difference(int []arr,int i,int j,int x)
{
int first = arr[i]-x;
int second = arr[j]-x;

if(first<0)
{
first=-first;
}
if(second<0)
{
second=-second;
}
if(first > second)
{
return j;
}
else
{
return i;
}
}
//Display k closest elements of value x in given array
public void closest_k(int []arr,int size,int x,int k)
{

if(k > size)
{
//invalid possibility
return;
}
//first sort array element
sort_element(arr,size);

int location=-1,back=0,i=0,temp=0;

//Find First element which is less than or equal to given value x
for (i = 0; i < size; ++i)
{
if(x <= arr[i])
{
location  = i;
break;
}
}

if(location==-1)
{
if(x > arr[size-1])
{
//point to last element
location = size-1;
}
else
{
//point to first element
location = 0;
}
}
back=location-1;
i = 0;
System.out.print(" Nearest "+k+" elements of value "+x+" is :\n");
while(i < k)
{
if(location <size && back>-1)
{
temp = difference(arr,back,location,x);

System.out.print(" "+arr[temp] );

if(temp == location)
{
location++;
}
else
{
back--;
}
i++;
}
else if(location < size)
{
System.out.print(" "+arr[location] );
location++;
i++;
}
else if(back>0)
{
System.out.print(" "+arr[location] );
back--;
i++;
}
}
System.out.print("\n");
}
public static void main(String[] args) {

MyHeap obj = new MyHeap();

//Define Collection of array elements
int []arr = {4, 2, 1, 10, 15, 17, 20 , 14, 5};

//Get the size of array
int size = arr.length;

// x is value
// k is size of closest element
int x = 9, k = 4;

obj.closest_k(arr,size,x,k);
}
}```
```

#### Output

`````` Nearest 4 elements of value 9 is :
10 5 4 14``````
``````/*
C# Program
Find k closest numbers in an unsorted array
*/
using System;

public class MyHeap {
//Swap two element in array
public void swap(int[] arr, int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
public int compare(int[] arr, int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
swap(arr, right, root);
location = right;
} else {
swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
swap(arr, right, root);
location = right;
}
return location;
}
public void heap(int[] arr, int size, int root) {
int left = 2 * root + 1;
int right = 2 * root + 2;
int next_in = compare(arr, left, right, root, size);
if (next_in != -1) {
heap(arr, size, next_in);
}
}
public void print_array(int[] arr, int size) {
Console.Write("\n");
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
}
public void sort_element(int[] arr, int size) {
for (int i = (size / 2) - 1; i >= 0; i--) {
heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--) {
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
public int difference(int[] arr, int i, int j, int x) {
int first = arr[i] - x;
int second = arr[j] - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
public void closest_k(int[] arr, int size, int x, int k) {
if (k > size) {
return;
}
sort_element(arr, size);
int location = -1, back = 0, i = 0, temp = 0;
//Find First element which is less than or equal to given value x

for (i = 0; i < size; ++i) {
if (x <= arr[i]) {
location = i;
break;;
}
}
if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
Console.Write(" Nearest " + k + " elements of value " + x + " is :\n");
while (i < k) {
if (location < size && back > -1) {
temp = difference(arr, back, location, x);
Console.Write(" " + arr[temp]);
if (temp == location) {
location++;
} else {
back--;
}
i++;
} else
if (location < size) {
Console.Write(" " + arr[location]);
location++;
i++;
} else
if (back > 0) {
Console.Write(" " + arr[location]);
back--;
i++;
}
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
int[]
//Define Collection of array elements
arr = {
4,
2,
1,
10,
15,
17,
20,
14,
5
};
//Get the size of array
int size = arr.Length;
// x is value
// k is size of closest element
int x = 9, k = 4;
obj.closest_k(arr, size, x, k);
}
}```
```

#### Output

`````` Nearest 4 elements of value 9 is :
10 5 4 14``````
``````<?php
/*
Php Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array

public 	function swap(&\$arr, \$first, \$second) {
\$auxiliary = \$arr[\$first];
\$arr[\$first] = \$arr[\$second];
\$arr[\$second] = \$auxiliary;
}
public 	function compare(&\$arr, \$left, \$right, \$root, \$size) {
\$location = -1;
if (\$left < \$size && \$arr[\$left] > \$arr[\$root]) {
if (\$right < \$size && \$arr[\$right] > \$arr[\$left]) {
\$this->swap(\$arr, \$right, \$root);
\$location = \$right;
} else {
\$this->swap(\$arr, \$left, \$root);
\$location = \$left;
}
} else
if (\$right < \$size && \$arr[\$right] > \$arr[\$root]) {
\$this->swap(\$arr, \$right, \$root);
\$location = \$right;
}
return \$location;
}
public 	function heap(&\$arr, \$size, \$root) {
\$left = 2 *\$root + 1;
\$right = 2 *\$root + 2;
\$next_in = \$this->compare(\$arr, \$left, \$right, \$root, \$size);
if (\$next_in != -1) {
\$this->heap(\$arr, \$size, \$next_in);
}
}
public 	function print_array(\$arr, \$size) {
echo("\n");
for (\$i = 0; \$i < \$size; \$i++) {
echo(" ". \$arr[\$i]);
}
}
public 	function sort_element(&\$arr, \$size) {
for (\$i = (intval(\$size / 2)) - 1; \$i >= 0; \$i--) {
\$this->heap(\$arr, \$size, \$i);
}
for (\$i = \$size - 1; \$i >= 0; \$i--) {
\$this->swap(\$arr, 0, \$i);
\$this->heap(\$arr, \$i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
public 	function difference(\$arr, \$i, \$j, \$x) {
\$first = \$arr[\$i] - \$x;
\$second = \$arr[\$j] - \$x;
if (\$first < 0) {
\$first = -\$first;
}
if (\$second < 0) {
\$second = -\$second;
}
if (\$first > \$second) {
return \$j;
} else {
return \$i;
}
}
//Display k closest elements of value x in given array
public 	function closest_k(&\$arr, \$size, \$x, \$k) {
if (\$k > \$size) {
return;
}
//first sort array element
\$this->sort_element(\$arr, \$size);
\$location = -1;
\$back = 0;
\$i = 0;
\$temp = 0;
//Find First element which is less than or equal to given value x
for (\$i = 0; \$i < \$size; ++\$i) {
if (\$x <= \$arr[\$i]) {
\$location = \$i;
break;
}
}
if (\$location == -1) {
if (\$x > \$arr[\$size - 1]) {
//point to last element
\$location = \$size - 1;
} else {
//point to first element
\$location = 0;
}
}
\$back = \$location - 1;
\$i = 0;
echo(" Nearest ". \$k ." elements of value ". \$x ." is :\n");
while (\$i < \$k) {
if (\$location < \$size && \$back > -1) {
\$temp = \$this->difference(\$arr, \$back, \$location, \$x);
echo(" ". \$arr[\$temp]);
if (\$temp == \$location) {
\$location++;
} else {
\$back--;
}
\$i++;
} else
if (\$location < \$size) {
echo(" ". \$arr[\$location]);
\$location++;
\$i++;
} else
if (\$back > 0) {
echo(" ". \$arr[\$location]);
\$back--;
\$i++;
}
}
echo("\n");
}
}

function main() {
\$obj = new MyHeap();
//Define Collection of array elements
\$arr = array(4, 2, 1, 10, 15, 17, 20, 14, 5);
//Get the size of array
\$size = count(\$arr);
// x is value
// k is size of closest element
\$x = 9;
\$k = 4;
\$obj->closest_k(\$arr, \$size, \$x, \$k);

}
main();```
```

#### Output

`````` Nearest 4 elements of value 9 is :
10 5 4 14``````
``````/*
Node Js Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array
swap(arr, first, second) {
var auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
compare(arr, left, right, root, size) {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this.swap(arr, right, root);
location = right;
}

return location;
}
heap(arr, size, root) {
var left = 2 *root + 1;
var right = 2 *root + 2;
var next_in = this.compare(arr, left, right, root, size);
if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
print_array(arr, size) {
process.stdout.write("\n");
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
}
sort_element(arr, size) {
for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
this.heap(arr, size, i);
}

for (var i = size - 1; i >= 0; i--) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
}
}

//Compare the value of i and j to value x and return smallest difference location
difference(arr, i, j, x) {
var first = arr[i] - x;
var second = arr[j] - x;
if (first < 0) {
first = -first;
}

if (second < 0) {
second = -second;
}

if (first > second) {
return j;
} else {
return i;
}
}

//Display k closest elements of value x in given array
closest_k(arr, size, x, k) {
if (k > size) {
return;
}

//first sort array element
this.sort_element(arr, size);
var location = -1;
var back = 0;
var i = 0;
var temp = 0;
//Find First element which is less than or equal to given value x

for (i = 0; i < size; ++i) {
if (x <= arr[i]) {
location = i;
break;
}
}

if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
process.stdout.write(" Nearest " + k + " elements of value " + x + " is :\n");
while (i < k) {
if (location < size && back > -1) {
temp = this.difference(arr, back, location, x);
process.stdout.write(" " + arr[temp]);
if (temp == location) {
location++;
} else {
back--;
}
i++;
} else
if (location < size) {
process.stdout.write(" " + arr[location]);
location++;
i++;
} else
if (back > 0) {
process.stdout.write(" " + arr[location]);
back--;
i++;
}
}

process.stdout.write("\n");
}
}

function main(args) {
var obj = new MyHeap();
//Define Collection of array elements
var arr = [4, 2, 1, 10, 15, 17, 20, 14, 5];
//Get the size of array
var size = arr.length;
// x is value
// k is size of closest element
var x = 9;
var k = 4;
obj.closest_k(arr, size, x, k);
}

main();```
```

#### Output

`````` Nearest 4 elements of value 9 is :
10 5 4 14``````
``````# Python 3 Program
# Find k closest numbers in an unsorted array
class MyHeap :
# Swap two element in array
def swap(self, arr, first, second) :
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary

def compare(self, arr, left, right, root, size) :
location = -1
if (left < size and arr[left] > arr[root]) :
if (right < size and arr[right] > arr[left]) :
self.swap(arr, right, root)
location = right
else :
self.swap(arr, left, root)
location = left

elif (right < size and arr[right] > arr[root]) :
self.swap(arr, right, root)
location = right

return location

def heap(self, arr, size, root) :
left = 2 * root + 1
right = 2 * root + 2
next_in = self.compare(arr, left, right, root, size)
if (next_in != -1) :
self.heap(arr, size, next_in)

def print_array(self, arr, size) :
print("\n", end = "")
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

def sort_element(self, arr, size) :
i = (int(size / 2)) - 1
while (i >= 0) :
self.heap(arr, size, i)
i -= 1

i = size - 1
while (i >= 0) :
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1

# Compare the value of i and j to value x and return smallest difference location
def difference(self, arr, i, j, x) :
first = arr[i] - x
second = arr[j] - x
if (first < 0) :
first = -first

if (second < 0) :
second = -second

if (first > second) :
return j
else :
return i

# Display k closest elements of value x in given array
def closest_k(self, arr, size, x, k) :
if (k > size) :
return

self.sort_element(arr, size)
location = -1
back = 0
i = 0
temp = 0
# Find First element which is less than or equal to given value x
i = 0
while (i < size) :
if (x <= arr[i]) :
location = i
break

i += 1

if (location == -1) :
if (x > arr[size - 1]) :
# point to last element
location = size - 1
else :
# point to first element
location = 0

back = location - 1
i = 0
print(" Nearest ", k ," elements of value ", x ," is :\n", end = "")
while (i < k) :
if (location < size and back > -1) :
temp = self.difference(arr, back, location, x)
print(" ", arr[temp], end = "")
if (temp == location) :
location += 1
else :
back -= 1

i += 1
elif (location < size) :
print(" ", arr[location], end = "")
location += 1
i += 1
elif (back > 0) :
print(" ", arr[location], end = "")
back -= 1
i += 1

print("\n", end = "")

def main() :
obj = MyHeap()
# Define Collection of array elements
arr = [4, 2, 1, 10, 15, 17, 20, 14, 5]
# Get the size of array
size = len(arr)
#  k is size of closest element
#  x is value
#  k is size of closest element
x = 9
k = 4
obj.closest_k(arr, size, x, k)

if __name__ == "__main__":
main()```
```

#### Output

`````` Nearest  4  elements of value  9  is :
10  5  4  14``````
``````# Ruby Program
# Find k closest numbers in an unsorted array
class MyHeap
# Swap two element in array
def swap(arr, first, second)
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
end
def compare(arr, left, right, root, size)
location = -1
if (left < size && arr[left] > arr[root])
if (right < size && arr[right] > arr[left])
self.swap(arr, right, root)
location = right
else
self.swap(arr, left, root)
location = left
end
elsif (right < size && arr[right] > arr[root])
self.swap(arr, right, root)
location = right

end
return location
end
def heap(arr, size, root)
left = 2 * root + 1
right = 2 * root + 2
next_in = self.compare(arr, left, right, root, size)
if (next_in != -1)
self.heap(arr, size, next_in)
end
end
def print_array(arr, size)
print("\n")
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
def sort_element(arr, size)
i = (size / 2) - 1
while (i >= 0)
self.heap(arr, size, i)
i -= 1
end
i = size - 1
while (i >= 0)
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
end
end
# Compare the value of i and j to value x and return smallest difference location
def difference(arr, i, j, x)
first = arr[i] - x
second = arr[j] - x
if (first < 0)
first = -first
end
if (second < 0)
second = -second
end
if (first > second)
return j
else
return i
end
end
# Display k closest elements of value x in given array
def closest_k(arr, size, x, k)
if (k > size)
return
end
self.sort_element(arr, size)
location = -1
back = 0
i = 0
temp = 0
# Find First element which is less than or equal to given value x
i = 0
while (i < size)
if (x <= arr[i])
location = i
break
end
i += 1
end
if (location == -1)
if (x > arr[size - 1])
# point to last element
location = size - 1
else
# point to first element
location = 0
end
end
back = location - 1
i = 0
print(" Nearest ", k ," elements of value ", x ," is  :\n")
while (i < k)
if (location < size && back > -1)
temp = self.difference(arr, back, location, x)
print(" ", arr[temp])
if (temp == location)
location += 1
else
back -= 1
end
i += 1
elsif (location < size)
print(" ", arr[location])
location += 1
i += 1
elsif (back > 0)
print(" ", arr[location])
back -= 1
i += 1
end
end
print("\n")
end
end
def main()
obj = MyHeap.new()
# Define Collection of array elements
arr = [4, 2, 1, 10, 15, 17, 20, 14, 5]
# Get the size of array
size = arr.length
#  k is size of closest element
#  x is value
#  k is size of closest element
x = 9
k = 4
obj.closest_k(arr, size, x, k)
end
main()```
```

#### Output

`````` Nearest 4 elements of value 9 is  :
10 5 4 14
``````
``````/*
Scala Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array
def swap(arr: Array[Int], first: Int, second: Int): Unit = {
val auxiliary: Int = arr(first);
arr(first) = arr(second);
arr(second) = auxiliary;
}
def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
var location: Int = -1;

if (left < size && arr(left) > arr(root)) {
if (right < size && arr(right) > arr(left)) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr(right) > arr(root)) {
this.swap(arr, right, root);
location = right;
}
return location;
}
def heap(arr: Array[Int], size: Int, root: Int): Unit = {
val left: Int = 2 * root + 1;
val right: Int = 2 * root + 2;
val next_in: Int = this.compare(arr, left, right, root, size);

if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
def print_array(arr: Array[Int], size: Int): Unit = {
print("\n");
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
}
def sort_element(arr: Array[Int], size: Int): Unit = {
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0) {
this.heap(arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
i -= 1;
}
}
//Compare the value of i and j to value x and return smallest difference location
def difference(arr: Array[Int], i: Int, j: Int, x: Int): Int = {
var first: Int = arr(i) - x;
var second: Int = arr(j) - x;

if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
def closest_k(arr: Array[Int], size: Int, x: Int, k: Int): Unit = {
if (k > size) {
return;
}
this.sort_element(arr, size);
var location: Int = -1;
var back: Int = 0;
var i: Int = 0;
var temp: Int = 0;

//Find First element which is less than or equal to given value x
i = 0;
while (i < size && location == -1) {
if (x <= arr(i)) {
location = i;
}
i += 1;
}
if (location == -1) {
if (x > arr(size - 1)) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
print(" Nearest " + k + " elements of value " + x + " is :\n");
while (i < k) {
if (location < size && back > -1) {
temp = this.difference(arr, back, location, x);
print(" " + arr(temp));

if (temp == location) {
location += 1;
} else {
back -= 1;
}
i += 1;
} else
if (location < size) {
print(" " + arr(location));
location += 1;
i += 1;
} else
if (back > 0) {
print(" " + arr(location));
back -= 1;
i += 1;
}
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();

//Define Collection of array elements
var arr: Array[Int] = Array(4, 2, 1, 10, 15, 17, 20, 14, 5);

//Get the size of array
val size: Int = arr.length;

// x is value
// k is size of closest element
val x: Int = 9;
val k: Int = 4;
obj.closest_k(arr, size, x, k);
}
}```
```

#### Output

`````` Nearest 4 elements of value 9 is :
10 5 4 14``````
``````/*
Swift Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array
func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
let auxiliary: Int = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
var location: Int = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
self.swap(&arr, right, root);
location = right;
} else {
self.swap(&arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
self.swap(&arr, right, root);
location = right;
}
return location;
}
func heap(_ arr: inout [Int], _ size: Int, _ root: Int) {
let left: Int = 2 * root + 1;
let right: Int = 2 * root + 2;
let next_in: Int = self.compare(&arr, left, right, root, size);
if (next_in != -1) {
self.heap(&arr, size, next_in);
}
}
func print_array(_ arr: [Int], _ size: Int) {
print("\n", terminator: "");
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
}
func sort_element(_ arr: inout [Int], _ size: Int) {
var i: Int = (size / 2) - 1;
while (i >= 0) {
self.heap(&arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
self.swap(&arr, 0, i);
self.heap(&arr, i, 0);
i -= 1;
}
}
//Compare the value of i and j to value x and return smallest difference location
func difference(_ arr: [Int], _ i: Int, _ j: Int, _ x: Int) -> Int {
var first: Int = arr[i] - x;
var second: Int = arr[j] - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
func closest_k(_ arr: inout [Int], _ size: Int, _ x: Int, _ k: Int) {
if (k > size) {
return;
}
self.sort_element(&arr, size);
var location: Int = -1;
var back: Int = 0;
var i: Int = 0;
var temp: Int = 0;
//Find First element which is less than or equal to given value x
i = 0;
while (i < size) {
if (x <= arr[i]) {
location = i;
break;
}
i += 1;
}
if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
print(" Nearest ", k ," elements of value ", x ," is :\n", terminator: "");
while (i < k) {
if (location < size && back > -1) {
temp = self.difference(arr, back, location, x);
print(" ", arr[temp], terminator: "");
if (temp == location) {
location += 1;
} else {
back -= 1;
}
i += 1;
} else
if (location < size) {
print(" ", arr[location], terminator: "");
location += 1;
i += 1;
} else
if (back > 0) {
print(" ", arr[location], terminator: "");
back -= 1;
i += 1;
}
}
print("\n", terminator: "");
}
}
func main() {
let obj: MyHeap = MyHeap();
//Define Collection of array elements
var arr: [Int] = [4, 2, 1, 10, 15, 17, 20, 14, 5];
//Get the size of array
let size: Int = arr.count;
// x is value
// k is size of closest element
let x: Int = 9;
let k: Int = 4;
obj.closest_k(&arr, size, x, k);
}
main();```
```

#### Output

`````` Nearest  4  elements of value  9  is :
10  5  4  14``````

## Time Complexity

• The heap sort operation has an average and worst-case time complexity of O(n log n), where n is the size of the array.
• Finding the initial location takes O(n) time.
• Finding the K closest elements takes O(k log n) time.
• Overall, the time complexity is dominated by the sorting step, so the total time complexity is O(n log n).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post