Find k largest elements in array
In various applications, the task of finding the K largest elements from an array is common. This problem involves identifying and displaying the K largest elements from an unsorted array. A common approach to solving this problem is using a heap-based strategy. In this article, we'll explore a C program that employs this approach to efficiently find and present the K largest elements in an array.
Problem Statement and Description
Given an array and an integer K, the goal is to find and display the K largest elements from the array. Since
the array is unsorted, we need a mechanism to efficiently identify the K largest 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
largest elements from this array.
Idea to Solve the Problem
To tackle this problem, we can use a max-heap-based approach. The main steps are:
- Build a max-heap on the array elements.
- For each iteration, swap the root element (largest element) with the last element of the heap and fix the heap.
- Repeat the swapping and heap-fixing process for the remaining unsorted part of the heap.
- The first K elements of the heap now contain the K largest 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_largest(arr, size, k)
build max-heap on 'arr'
for i from size-1 to size-1 - k
swap arr[0] with arr[i]
fix max-heap on arr for elements up to i
print "K Largest Elements:"
print last 'k' elements of 'arr'
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_largest(arr, size, k)
Algorithm Explanation
- The
swap
function swaps two elements in the array. - The
compare
function compares the elements at indicesleft
andright
with the element at indexroot
and returns the index of the larger element. - The
heap
function creates a max-heap by comparing elements and swapping them if needed. - The
k_largest
function builds a max-heap on the array, swaps and fixes the heap to find the K largest elements. - The
main
function initializes the array, prints the original array, and then calls thek_largest
function to find and display the K largest elements.
Code Solution
//C Program
//Find k 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 all k largest element in array
void k_largest(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 >= (size-1 -k); i--)
{
//Swap large element at the end
swap(auxiliary, 0, i);
heap(auxiliary, i, 0);
}
printf("\n %d Largest Element \n",k);
//Display resultant elements
for (int i = size-1; i >= size-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 largest element
int k=3;
print_data(arr,size);
k_largest(arr,size,k);
return 0;
}
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
/*
C++ Program
Find k 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) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
cout << "\n";
}
//Finding the all k largest element in array
void k_largest(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--) {
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 << " " << k << " Largest Element \n";
//Display resultant elements
for (int i = size - 1; i >= size - 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 largest element
int k = 3;
//Display array elements
obj.print_data(arr, size);
obj.k_largest(arr, size, k);
return 0;
}
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
/*
Java Program
Find k 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)
{
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
System.out.print("\n");
}
//Finding the all k largest element in array
public void k_largest(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 >= (size-1 -k); i--)
{
//Swap large element at the end
swap(auxiliary, 0, i);
heap(auxiliary, i, 0);
}
System.out.print(" "+k+" Largest Element \n");
//Display resultant elements
for (int i = size-1; i >= size-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 largest element
int k=3;
//Display array elements
obj.print_data(arr,size);
obj.k_largest(arr,size,k);
}
}
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
/*
C# Program
Find k 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) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Finding the all k largest element in array
public void k_largest(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 >= (size - 1 - k); i--) {
swap(auxiliary, 0, i);
heap(auxiliary, i, 0);
}
Console.Write(" " + k + " Largest Element \n");
//Display resultant elements
for (int i = size - 1; i >= size - 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 largest element
int k = 3;
obj.print_data(arr, size);
obj.k_largest(arr, size, k);
}
}
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
<?php
/*
Php Program
Find k 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) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
echo("\n");
}
//Finding the all k largest element in array
public function k_largest($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 >= ($size - 1 - $k); $i--) {
//Swap large element at the end
$this->swap($auxiliary, 0, $i);
$this->heap($auxiliary, $i, 0);
}
echo(" ". $k ." Largest Element \n");
//Display resultant elements
for ($i = $size - 1; $i >= $size - $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 largest element
$k = 3;
//Display array elements
$obj->print_data($arr, $size);
$obj->k_largest($arr, $size, $k);
}
main();
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
/*
Node Js Program
Find k 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) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Finding the all k largest element in array
k_largest(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 >= (size - 1 - k); i--) {
//Swap large element at the end
this.swap(auxiliary, 0, i);
this.heap(auxiliary, i, 0);
}
process.stdout.write(" " + k + " Largest Element \n");
//Display resultant elements
for (var i = size - 1; i >= size - 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 largest element
var k = 3;
//Display array elements
obj.print_data(arr, size);
obj.k_largest(arr, size, k);
}
main();
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
# Python 3 Program
# Find k 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) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
# Finding the all k largest element in array
def k_largest(self, arr, size, k) :
if (k > size) :
return
i = 0
auxiliary = [0] * size
# set initial values into the auxiliary array
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(" ", k ," Largest Element \n", end = "")
# Display resultant elements
i = size - 1
while (i >= size - 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 largest element
k = 3
# Display array elements
obj.print_data(arr, size)
obj.k_largest(arr, size, k)
if __name__ == "__main__":
main()
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
# Ruby Program
# Find k 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)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Finding the all k largest element in array
def k_largest(arr, size, k)
if (k > size)
return
end
i = 0
auxiliary = Array.new(size, 0)
# set initial values into the auxiliary array
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(" ", k ," Largest Element \n")
# Display resultant elements
i = size - 1
while (i >= size - 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 largest element
k = 3
# Display array elements
obj.print_data(arr, size)
obj.k_largest(arr, size, k)
end
main()
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
/*
Scala Program
Find k 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 = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Finding the all k largest element in array
def k_largest(arr: Array[Int], size: Int, k: Int): Unit = {
if (k > size) {
return;
}
var i: Int = 0;
var auxiliary: Array[Int] = Array.fill[Int](size)(0);
//set initial values into the auxiliary array
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(" " + k + " Largest Element \n");
//Display resultant elements
i = size - 1;
while (i >= size - 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 largest element
val k: Int = 3;
//Display array elements
obj.print_data(arr, size);
obj.k_largest(arr, size, k);
}
}
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
/*
Swift Program
Find k 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) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Finding the all k largest element in array
func k_largest(_ arr: [Int], _ size: Int, _ k: Int) {
if (k > size) {
return;
}
var i: Int = 0;
var auxiliary: [Int] = Array(repeating: 0, count: size);
//set initial values into the auxiliary array
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(" ", k ," Largest Element \n", terminator: "");
//Display resultant elements
i = size - 1;
while (i >= size - k) {
print(" ", auxiliary[i], terminator: "");
i -= 1;
}
print(terminator: "\n");
}
}
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 largest element
let k: Int = 3;
//Display array elements
obj.print_data(arr, size);
obj.k_largest(arr, size, k);
}
main();
Output
6 8 2 7 14 1 3 8 21 11 12 5
3 Largest Element
21 14 12
Output Explanation
For the given array arr = {6, 8, 2, 7, 14, 1, 3, 8, 21, 11, 12, 5}
and K = 3, the output will be:
Original Array:
6 8 2 7 14 1 3 8 21 11 12 5
K Largest Elements:
21 14 12
This means that the 3 largest elements in the array are 21, 14, and 12.
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.
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