Skip to main content

Find k smallest elements in array

In various scenarios, you might need to identify the K smallest elements from an array. This problem entails selecting the K smallest elements from an unsorted array and presenting them in ascending order. In this article, we'll delve into a C program that tackles this problem using a heap-based approach.

Problem Statement and Description

Given an array and an integer K, the task is to find and display the K smallest elements from the array. The array is unsorted, so we'll sort it using a max-heap approach to efficiently retrieve the smallest elements. For instance, consider the array arr = {6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5} and K = 3. We aim to find the 3 smallest elements from this array.

Idea to Solve the Problem

To address this challenge, we'll utilize a max-heap-based approach. The primary steps involved are:

  1. Sort the array using a max-heap sort.
  2. Initialize an auxiliary array to store the sorted elements temporarily.
  3. Build a max-heap on the auxiliary array.
  4. Swap the largest element (root) with the last element of the heap and fix the heap.
  5. Repeat the swapping and heap-fixing process for the remaining unsorted part of the heap.
  6. The first K elements of the auxiliary array now contain the K smallest 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 larger element

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

function k_smallest(arr, size, k)
    auxiliary = new array of size 'size'
    copy elements of 'arr' to 'auxiliary'
    build max-heap on 'auxiliary'
    for i from size-1 to 0
    swap auxiliary[0] with auxiliary[i]
    fix max-heap on auxiliary for elements up to i
    print "K Smallest Elements:"
    print first 'k' elements of 'auxiliary'

function main()
    arr = {6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5}
    size = sizeof(arr) / sizeof(arr[0])
    k = 3
    print "Original Array:"
    print arr
    k_smallest(arr, size, 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 larger element.
  3. The heap function creates a max-heap by comparing elements and swapping them if needed.
  4. The k_smallest function creates an auxiliary array, builds a max-heap on it, and then swaps and fixes the heap to find the K smallest elements.
  5. The main function initializes the array, prints the original array, and then calls the k_smallest function to find and display the K smallest elements.

Code Solution

//C Program
//Find k smallest elements in array
#include <stdio.h>

//Swap two element in array
void swap(int arr[],int first,int second)
{
  int temp=arr[first];
  arr[first]=arr[second];
  arr[second]=temp;
}
//Check the properties of max heap
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;
}
//Perform max heap sort
void heap(int arr[],int size,int root)
{
  //Get location of left and right child
  int left  = 2*root+1;
  int right = 2*root+2;
 
  int next_in = compare(arr, left, right, root, size);
 
  if(next_in != -1)
  {
    //When array is modified then check other array elements
    heap(arr,size,next_in);
  }
}
//Display array elements
void print_data(int arr[],int size)
{
  printf("\n");
  for(int i = 0; i < size; i++)
  {
    printf("%3d",arr[i] );
  }
}

//Finding the all k smallest element in array
void k_smallest(int arr[],int size,int k)
{

  if(k>size)
  {
    return;
  }
  //Auxiliary memory that will be used to store array elements
  int auxiliary[size];

  //set initial values into the auxiliary array
  for (int i = 0; i < size; ++i)
  {
    auxiliary[i] = arr[i];
  }


  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap(auxiliary,size,i);
  }


  for (int i = size-1; i >= 0; i--)
  {
    //Swap large element at the end
    swap(auxiliary, 0, i);
    heap(auxiliary, i, 0);
  }


  printf("\n  %d Smallest Element \n",k);

  //Display resultant elements
  for (int i = 0; i < k; ++i)
  {
    printf("  %d",auxiliary[i] );
  }
  printf("\n");
}
int main()
{
  //Define collection of array elements
  int arr[] = {6, 8, 2, 7,14,  1, 3, 8, 21, 11, 12 ,5};

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

  //number of smallest element
  int k=3;

  print_data(arr,size);

  k_smallest(arr,size,k);
 
  return 0;
}

Output

  6  8  2  7 14  1  3  8 21 11 12  5
  3 Smallest Element
  1  2  3
/*
  C++ Program
  Find k smallest elements in array
*/
#include<iostream>
using namespace std;

class MyHeap {
	public:

    //Swap two element in array
    void swap(int arr[], int first, int second) {
      int temp = arr[first];
      arr[first] = arr[second];
      arr[second] = temp;
    }
	//Check the properties of max heap
	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;
	}
	//Perform max heap sort
	void heap(int arr[], int size, int root) {
		//Get location of left and right child
		int left = 2 *root + 1;
		int right = 2 *root + 2;
		int next_in = this->compare(arr, left, right, root, size);
		if (next_in != -1) {
			//When array is modified then check other array elements
			this->heap(arr, size, next_in);
		}
	}
	//Display array elements
	void print_data(int arr[], int size) {
		for (int i = 0; i < size; i++) {
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	//Finding the all k smallest element in array
	void k_smallest(int arr[], int size, int k) {
		if (k > size) {
			return;
		}
		int *auxiliary = new int[size];
		//set initial values into the auxiliary array

		for (int i = 0; i < size; ++i) {
			auxiliary[i] = arr[i];
		}
		for (int i = (size / 2) - 1; i >= 0; i--) {
			this->heap(auxiliary, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			//Swap large element at the end
			this->swap(auxiliary, 0, i);
			this->heap(auxiliary, i, 0);
		}
		cout << " " << k << " Smallest Element \n";
		//Display resultant elements

		for (int i = 0; i < k; ++i) {
			cout << " " << auxiliary[i];
		}
		cout << "\n";
	}
};
int main() {
	MyHeap obj = MyHeap();
	int arr[] = {
		6,
		8,
		2,
		7,
		14,
		1,
		3,
		8,
		21,
		11,
		12,
		5
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	//Number of smallest element
	int k = 3;
	//Display array elements
	obj.print_data(arr, size);
	obj.k_smallest(arr, size, k);
	return 0;
}

Output

 6 8 2 7 14 1 3 8 21 11 12 5
 3 Smallest Element
 1 2 3
/*
  Java Program
  Find k smallest elements in array
*/
public class MyHeap {

  //Swap two element in array
  public void swap(int []arr,int first,int second)
  {
    int temp=arr[first];
    arr[first]=arr[second];
    arr[second]=temp;
  }
  //Check the properties of max heap
  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;
  }
  //Perform max heap sort
  public void heap(int []arr,int size,int root)
  {
    //Get location of left and right child
    int left  = 2*root+1;
    int right = 2*root+2;
   
    int next_in = compare(arr, left, right, root, size);
   
    if(next_in != -1)
    {
      //When array is modified then check other array elements
      heap(arr,size,next_in);
    }
  }
  //Display array elements
  public void print_data(int []arr,int size)
  {
    
    for(int i = 0; i < size; i++)
    {
      System.out.print("  "+arr[i] );
    }
    System.out.print("\n");
  }

  //Finding the all k smallest element in array
  public void k_smallest(int []arr,int size,int k)
  {

    if(k>size)
    {
      return;
    }
    //Auxiliary memory that will be used to store array elements
    int []auxiliary= new int[size];

    //set initial values into the auxiliary array
    for (int i = 0; i < size; ++i)
    {
      auxiliary[i] = arr[i];
    }

    for (int i = (size/2)-1; i >= 0; i--)
    {
      heap(auxiliary,size,i);
    }

    for (int i = size-1; i >= 0; i--)
    {
      //Swap large element at the end
      swap(auxiliary, 0, i);
      heap(auxiliary, i, 0);
    }

    System.out.print("  "+k+" Smallest Element \n");

    //Display resultant elements
    for (int i = 0; i <k; ++i)
    {
      System.out.print("  "+auxiliary[i] );
    }
    System.out.print("\n");
  }
  public static void main(String[] args) {
    
    MyHeap obj = new MyHeap();
    
    //Define Collection of array elements
    int []arr =  {6, 8, 2, 7,14,  1, 3, 8, 21, 11, 12 ,5};

    //Get the size of array
    int size = arr.length;
    
    //Number of smallest element
    int k=3;

    //Display array elements
    obj.print_data(arr,size);

    obj.k_smallest(arr,size,k);
  }
}

Output

 6 8 2 7 14 1 3 8 21 11 12 5
 3 Smallest Element
  1  2  3
/*
  C# Program
  Find k smallest elements in array
*/
using System;

public class MyHeap {
	//Swap two element in array
	public void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	//Check the properties of max heap
	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;
	}
	//Perform max heap sort
	public void heap(int[] arr, int size, int root) {
		//Get location of left and right child
		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);
		}
	}
	//Display array elements
	public void print_data(int[] arr, int size) {
		for (int i = 0; i < size; i++) {
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//Finding the all k smallest element in array
	public void k_smallest(int[] arr, int size, int k) {
		if (k > size) {
			return;
		}
		int[]
		//Auxiliary memory that will be used to store array elements
		auxiliary = new int[size];
		//set initial values into the auxiliary array

		for (int i = 0; i < size; ++i) {
			auxiliary[i] = arr[i];
		}
		for (int i = (size / 2) - 1; i >= 0; i--) {
			heap(auxiliary, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			swap(auxiliary, 0, i);
			heap(auxiliary, i, 0);
		}
		Console.Write(" " + k + " Smallest Element \n");
		//Display resultant elements

		for (int i = 0; i < k; ++i) {
			Console.Write(" " + auxiliary[i]);
		}
		Console.Write("\n");
	}
	public static void Main(String[] args) {
		MyHeap obj = new MyHeap();
		int[]
		//Define Collection of array elements
		arr = {
			6,
			8,
			2,
			7,
			14,
			1,
			3,
			8,
			21,
			11,
			12,
			5
		};
		//Get the size of array
		int size = arr.Length;
		//Number of smallest element
		int k = 3;
		obj.print_data(arr, size);
		obj.k_smallest(arr, size, k);
	}
}

Output

 6 8 2 7 14 1 3 8 21 11 12 5
 3 Smallest Element
 1 2 3
<?php
/*
  Php Program
  Find k smallest elements in array
*/
class MyHeap {
	//Swap two element in array
	public 	function swap(&$arr, $first, $second) {
		$temp = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $temp;
	}
	//Check the properties of max heap
	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;
	}
	//Perform max heap sort
	public 	function heap(&$arr, $size, $root) {
		//Get location of left and right child
		$left = 2 *$root + 1;
		$right = 2 *$root + 2;
		$next_in = $this->compare($arr, $left, $right, $root, $size);
		if ($next_in != -1) {
			//When array is modified then check other array elements
			$this->heap($arr, $size, $next_in);
		}
	}
	//Display array elements
	public 	function print_data($arr, $size) {
		for ($i = 0; $i < $size; $i++) {
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
	//Finding the all k smallest element in array
	public 	function k_smallest($arr, $size, $k) {
		if ($k > $size) {
			return;
		}
		//Auxiliary memory that will be used to store array elements
		$auxiliary = array_fill(0, $size, 0);
		//set initial values into the auxiliary array
		for ($i = 0; $i < $size; ++$i) {
			$auxiliary[$i] = $arr[$i];
		}
		for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
			$this->heap($auxiliary, $size, $i);
		}
		for ($i = $size - 1; $i >= 0; $i--) {
			//Swap large element at the end
			$this->swap($auxiliary, 0, $i);
			$this->heap($auxiliary, $i, 0);
		}
		echo(" ". $k ." Smallest Element \n");
		//Display resultant elements
		for ($i = 0; $i < $k; ++$i) {
			echo(" ". $auxiliary[$i]);
		}
		echo("\n");
	}
}

function main() {
	$obj = new MyHeap();
	//Define Collection of array elements
	$arr = array(6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5);
	//Get the size of array
	$size = count($arr);
	//Number of smallest element
	$k = 3;
	//Display array elements
	$obj->print_data($arr, $size);
	$obj->k_smallest($arr, $size, $k);

}
main();

Output

 6 8 2 7 14 1 3 8 21 11 12 5
 3 Smallest Element
 1 2 3
/*
  Node Js Program
  Find k smallest elements in array
*/
class MyHeap {
	//Swap two element in array
	swap(arr, first, second) {
		var temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}

	//Check the properties of max heap
	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;
	}

	//Perform max heap sort
	heap(arr, size, root) {
		//Get location of left and right child
		var left = 2 *root + 1;
		var right = 2 *root + 2;
		var next_in = this.compare(arr, left, right, root, size);
		if (next_in != -1) {
			//When array is modified then check other array elements
			this.heap(arr, size, next_in);
		}
	}

	//Display array elements
	print_data(arr, size) {
		for (var i = 0; i < size; i++) {
			process.stdout.write(" " + arr[i]);
		}

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

	//Finding the all k smallest element in array
	k_smallest(arr, size, k) {
		if (k > size) {
			return;
		}

		//Auxiliary memory that will be used to store array elements
		var auxiliary = Array(size).fill(0);
		//set initial values into the auxiliary array

		for (var i = 0; i < size; ++i) {
			auxiliary[i] = arr[i];
		}

		for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
			this.heap(auxiliary, size, i);
		}

		for (var i = size - 1; i >= 0; i--) {
			//Swap large element at the end
			this.swap(auxiliary, 0, i);
			this.heap(auxiliary, i, 0);
		}

		process.stdout.write(" " + k + " Smallest Element \n");
		//Display resultant elements

		for (var i = 0; i < k; ++i) {
			process.stdout.write(" " + auxiliary[i]);
		}

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

function main(args) {
	var obj = new MyHeap();
	//Define Collection of array elements
	var arr = [6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5];
	//Get the size of array
	var size = arr.length;
	//Number of smallest element
	var k = 3;
	//Display array elements
	obj.print_data(arr, size);
	obj.k_smallest(arr, size, k);
}

main();

Output

 6 8 2 7 14 1 3 8 21 11 12 5
 3 Smallest Element
 1 2 3
# Python 3 Program
# Find k smallest elements in array
class MyHeap :
	# Swap two element in array
	def swap(self, arr, first, second) :
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	
	# Check the properties of max heap
	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
	
	# Perform max heap sort
	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)
		
	
	# Display array elements
	def print_data(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	# Finding the all k smallest element in array
	def k_smallest(self, arr, size, k) :
		if (k > size) :
			return
		
		auxiliary = [0] * size
		# set initial values into the auxiliary array
		i = 0
		while (i < size) :
			auxiliary[i] = arr[i]
			i += 1
		
		i = (int(size / 2)) - 1
		while (i >= 0) :
			self.heap(auxiliary, size, i)
			i -= 1
		
		i = size - 1
		while (i >= 0) :
			self.swap(auxiliary, 0, i)
			self.heap(auxiliary, i, 0)
			i -= 1
		
		print(" ", k ," Smallest Element \n", end = "")
		# Display resultant elements
		i = 0
		while (i < k) :
			print(" ", auxiliary[i], end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	obj = MyHeap()
	# Define Collection of array elements
	arr = [6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5]
	# Get the size of array
	size = len(arr)
	# Number of smallest element
	k = 3
	# Display array elements
	obj.print_data(arr, size)
	obj.k_smallest(arr, size, k)


if __name__ == "__main__":
	main()

Output

  6  8  2  7  14  1  3  8  21  11  12  5
  3  Smallest Element
  1  2  3
# Ruby Program
# Find k smallest elements in array
class MyHeap 
	 # Swap two element in array
	def swap(arr, first, second) 
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	end
	 # Check the properties of max heap
	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
	 # Perform max heap sort
	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
	 # Display array elements
	def print_data(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	 # Finding the all k smallest element in array
	def k_smallest(arr, size, k) 
		if (k > size) 
			return
		end
		auxiliary = Array.new(size, 0)
		 # set initial values into the auxiliary array
		i = 0
		while (i < size) 
			auxiliary[i] = arr[i]
			i += 1
		end
		i = (size / 2) - 1
		while (i >= 0) 
			self.heap(auxiliary, size, i)
			i -= 1
		end
		i = size - 1
		while (i >= 0) 
			self.swap(auxiliary, 0, i)
			self.heap(auxiliary, i, 0)
			i -= 1
		end
		print(" ", k ," Smallest Element \n")
		 # Display resultant elements
		i = 0
		while (i < k) 
			print(" ", auxiliary[i])
			i += 1
		end
		print("\n")
	end
end
def main() 
	obj = MyHeap.new()
	 # Define Collection of array elements
	arr = [6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5]
	 # Get the size of array
	size = arr.length
	 # Number of smallest element
	k = 3
	 # Display array elements
	obj.print_data(arr, size)
	obj.k_smallest(arr, size, k)
end
main()

Output

 6 8 2 7 14 1 3 8 21 11 12 5
 3 Smallest Element 
 1 2 3

/*
  Scala Program
  Find k smallest elements in array
*/
class MyHeap {
	//Swap two element in array
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		val temp: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = temp;
	}
	//Check the properties of max heap
	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;
	}
	//Perform max heap sort
	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);
		}
	}
	//Display array elements
	def print_data(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size) {
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	//Finding the all k smallest element in array
	def k_smallest(arr: Array[Int], size: Int, k: Int): Unit = {
		if (k > size) {
			return;
		}
		var auxiliary: Array[Int] = Array.fill[Int](size)(0);

        //set initial values into the auxiliary array
        var i: Int = 0;
        while (i < size) {
            auxiliary(i) = arr(i);
            i += 1;
        }
        i = ((size / 2).toInt) - 1;
        while (i >= 0) {
            this.heap(auxiliary, size, i);
            i -= 1;
        }
        i = size - 1;
        while (i >= 0) {
            this.swap(auxiliary, 0, i);
            this.heap(auxiliary, i, 0);
            i -= 1;
        }
        print(" " + k + " Smallest Element \n");

        //Display resultant elements
        i = 0;
        while (i < k) {
            print(" " + auxiliary(i));
            i += 1;
        }
        print("\n");
    }
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyHeap = new MyHeap();

		//Define Collection of array elements
		val arr: Array[Int] = Array(6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5);

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

		//Number of smallest element
		val k: Int = 3;

		//Display array elements
		obj.print_data(arr, size);
		obj.k_smallest(arr, size, k);
	}
}

Output

 6 8 2 7 14 1 3 8 21 11 12 5
 3 Smallest Element
 1 2 3
/*
  Swift Program
  Find k smallest elements in array
*/
class MyHeap {
	//Swap two element in array
	func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
		let temp: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	//Check the properties of max heap
	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;
	}
	//Perform max heap sort
	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);
		}
	}
	//Display array elements
	func print_data(_ arr: [Int], _ size: Int) {
		var i: Int = 0;
		while (i < size) {
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Finding the all k smallest element in array
	func k_smallest(_ arr: [Int], _ size: Int, _ k: Int) {
		if (k > size) {
			return;
		}
		var auxiliary: [Int] = Array(repeating: 0, count: size);
        //set initial values into the auxiliary array
        var i: Int = 0;
        while (i < size) {
            auxiliary[i] = arr[i];
            i += 1;
        }
        i = (size / 2) - 1;
        while (i >= 0) {
            self.heap(&auxiliary, size, i);
            i -= 1;
        }
        i = size - 1;
        while (i >= 0) {
            self.swap(&auxiliary, 0, i);
            self.heap(&auxiliary, i, 0);
            i -= 1;
        }
        print(" ", k ," Smallest Element \n", terminator: "");
        //Display resultant elements
        i = 0;
        while (i < k) {
            print(" ", auxiliary[i], terminator: "");
            i += 1;
        }
        print("\n", terminator: "");
    }
}
func main() {
	let obj: MyHeap = MyHeap();
	//Define Collection of array elements
	let arr: [Int] = [6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5];
	//Get the size of array
	let size: Int = arr.count;
	//Number of smallest element
	let k: Int = 3;
	//Display array elements
	obj.print_data(arr, size);
	obj.k_smallest(arr, size, k);
}
main();

Output

  6  8  2  7  14  1  3  8  21  11  12  5
  3  Smallest Element
  1  2  3

Time Complexity

  • Building the max-heap takes O(n) time.
  • The loop for swapping and fixing the heap runs for n elements, and each iteration takes O(log n) time.
  • The total time complexity is dominated by building the heap and the loop, resulting in O(n log n) time complexity.
Last updated on by Kalkicode




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