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[0])
    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[0]);

  // 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[0]);
	// 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.

New Comment





Categories
Relative Post