Find kth largest element in array
Here given code implementation process.
//C Program
//Find kth largest 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 kth largest element in array
void kth_largest(int arr[],int size,int k)
{
if(k>size || k <=0)
{
//invalid position
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 >= (size-1 -k); i--)
{
//Swap large element at the end
swap(auxiliary, 0, i);
heap(auxiliary, i, 0);
}
printf("\n %d-th Largest Element is : ",k);
printf(" %d\n",auxiliary[size-k] );
}
int main()
{
//Define collection of array elements
int arr[] = {6, 8, 2, 7,14, 34, 1, 3, 9, 21, 11, 12 ,5};
//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);
//position of find largest element
int k = 5;
print_data(arr,size);
kth_largest(arr,size,k);
return 0;
}
Output
6 8 2 7 14 34 1 3 9 21 11 12 5
5-th Largest Element is : 11/*
C++ Program
Find kth largest 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) {
cout << "\n";
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
}
//Finding the kth largest element in array
void kth_largest(int arr[], int size, int k) {
if (k > size || k <= 0) {
//invalid position
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 >= (size - 1 - k); i--) {
//Swap large element at the end
this->swap(auxiliary, 0, i);
this->heap(auxiliary, i, 0);
}
cout << "\n " << k << "-th Largest Element is : ";
cout << " " << auxiliary[size - k] << "\n";
}
};
int main() {
MyHeap obj = MyHeap();
int arr[] = {
6,
8,
2,
7,
14,
34,
1,
3,
8,
21,
11,
12,
5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
//Number of largest element
int k = 5;
//Display array elements
obj.print_data(arr, size);
obj.kth_largest(arr, size, k);
return 0;
}
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5-th Largest Element is : 11/*
Java Program
Find kth largest 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)
{
System.out.print("\n");
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
}
//Finding the kth largest element in array
public void kth_largest(int []arr,int size,int k)
{
if(k>size || k <=0)
{
//invalid position
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 >= (size-1 -k); i--)
{
//Swap large element at the end
swap(auxiliary, 0, i);
heap(auxiliary, i, 0);
}
System.out.print("\n "+k+"-th Largest Element is : ");
System.out.print(" "+auxiliary[size-k]+"\n" );
}
public static void main(String[] args) {
MyHeap obj = new MyHeap();
//Define Collection of array elements
int []arr = {6, 8, 2, 7,14, 34, 1, 3, 8, 21, 11, 12 ,5};
//Get the size of array
int size = arr.length;
//Number of largest element
int k = 5;
//Display array elements
obj.print_data(arr,size);
obj.kth_largest(arr,size,k);
}
}
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5-th Largest Element is : 11/*
C# Program
Find kth largest 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) {
Console.Write("\n");
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
}
//Finding the kth largest element in array
public void kth_largest(int[] arr, int size, int k) {
if (k > size || k <= 0) {
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 >= (size - 1 - k); i--) {
swap(auxiliary, 0, i);
heap(auxiliary, i, 0);
}
Console.Write("\n " + k + "-th Largest Element is : ");
Console.Write(" " + auxiliary[size - k] + "\n");
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
int[]
//Define Collection of array elements
arr = {
6,
8,
2,
7,
14,
34,
1,
3,
8,
21,
11,
12,
5
};
//Get the size of array
int size = arr.Length;
//Number of largest element
int k = 5;
obj.print_data(arr, size);
obj.kth_largest(arr, size, k);
}
}
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5-th Largest Element is : 11<?php
/*
Php Program
Find kth largest 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) {
echo("\n");
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
}
//Finding the kth largest element in array
public function kth_largest($arr, $size, $k) {
if ($k > $size || $k <= 0) {
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 >= ($size - 1 - $k); $i--) {
//Swap large element at the end
$this->swap($auxiliary, 0, $i);
$this->heap($auxiliary, $i, 0);
}
echo("\n ". $k ."-th Largest Element is : ");
echo(" ". $auxiliary[$size - $k] ."\n");
}
}
function main() {
$obj = new MyHeap();
//Define Collection of array elements
$arr = array(6, 8, 2, 7, 14, 34, 1, 3, 8, 21, 11, 12, 5);
//Get the size of array
$size = count($arr);
//Number of largest element
$k = 5;
//Display array elements
$obj->print_data($arr, $size);
$obj->kth_largest($arr, $size, $k);
}
main();
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5-th Largest Element is : 11/*
Node Js Program
Find kth largest 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) {
process.stdout.write("\n");
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
}
//Finding the kth largest element in array
kth_largest(arr, size, k) {
if (k > size || k <= 0) {
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 >= (size - 1 - k); i--) {
//Swap large element at the end
this.swap(auxiliary, 0, i);
this.heap(auxiliary, i, 0);
}
process.stdout.write("\n " + k + "-th Largest Element is : ");
process.stdout.write(" " + auxiliary[size - k] + "\n");
}
}
function main(args) {
var obj = new MyHeap();
//Define Collection of array elements
var arr = [6, 8, 2, 7, 14, 34, 1, 3, 8, 21, 11, 12, 5];
//Get the size of array
var size = arr.length;
//Number of largest element
var k = 5;
//Display array elements
obj.print_data(arr, size);
obj.kth_largest(arr, size, k);
}
main();
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5-th Largest Element is : 11# Python 3 Program
# Find kth largest 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) :
print("\n", end = "")
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
# Finding the kth largest element in array
def kth_largest(self, arr, size, k) :
if (k > size or k <= 0) :
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 >= (size - 1 - k)) :
self.swap(auxiliary, 0, i)
self.heap(auxiliary, i, 0)
i -= 1
print("\n ", k ,"-th Largest Element is : ", end = "")
print(" ", auxiliary[size - k] ,"\n", end = "")
def main() :
obj = MyHeap()
arr = [6, 8, 2, 7, 14, 34, 1, 3, 8, 21, 11, 12, 5]
size = len(arr)
k = 5
obj.print_data(arr, size)
obj.kth_largest(arr, size, k)
if __name__ == "__main__":
main()
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5 -th Largest Element is : 11# Ruby Program
# Find kth largest 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)
print("\n")
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
# Finding the kth largest element in array
def kth_largest(arr, size, k)
if (k > size || k <= 0)
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 >= (size - 1 - k))
self.swap(auxiliary, 0, i)
self.heap(auxiliary, i, 0)
i -= 1
end
print("\n ", k ,"-th Largest Element is :")
print(" ", auxiliary[size - k] ,"\n")
end
end
def main()
obj = MyHeap.new()
arr = [6, 8, 2, 7, 14, 34, 1, 3, 8, 21, 11, 12, 5]
size = arr.length
k = 5
obj.print_data(arr, size)
obj.kth_largest(arr, size, k)
end
main()
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5-th Largest Element is : 11
/*
Scala Program
Find kth largest 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 = {
print("\n");
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
}
//Finding the kth largest element in array
def kth_largest(arr: Array[Int], size: Int, k: Int): Unit = {
if (k > size || k <= 0) {
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 >= (size - 1 - k)) {
this.swap(auxiliary, 0, i);
this.heap(auxiliary, i, 0);
i -= 1;
}
print("\n " + k + "-th Largest Element is : ");
print(" " + auxiliary(size - k) + "\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();
val arr: Array[Int] = Array(6, 8, 2, 7, 14, 34, 1, 3, 8, 21, 11, 12, 5);
val size: Int = arr.length;
val k: Int = 5;
obj.print_data(arr, size);
obj.kth_largest(arr, size, k);
}
}
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5-th Largest Element is : 11/*
Swift Program
Find kth largest 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) {
print("\n", terminator: "");
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
}
//Finding the kth largest element in array
func kth_largest(_ arr: [Int], _ size: Int, _ k: Int) {
if (k > size || k <= 0) {
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 >= (size - 1 - k)) {
self.swap(&auxiliary, 0, i);
self.heap(&auxiliary, i, 0);
i -= 1;
}
print("\n ", k ,"-th Largest Element is : ", terminator: "");
print(" ", auxiliary[size - k] );
}
}
func main() {
let obj: MyHeap = MyHeap();
let arr: [Int] = [6, 8, 2, 7, 14, 34, 1, 3, 8, 21, 11, 12, 5];
let size: Int = arr.count;
let k: Int = 5;
obj.print_data(arr, size);
obj.kth_largest(arr, size, k);
}
main();
Output
6 8 2 7 14 34 1 3 8 21 11 12 5
5 -th Largest Element is : 11
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