Write a function that prints the \(k^{th}\) largest elements in an array. Elements in array can be in any order.

For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., \(k\) = 3 then your program should print 50, 30 and 23.

Method:

• Build a Max Heap tree in \(O(n)\)
• Extract the max \(k\) times to get \(k\) maximum elements from the Max Heap in \(O(k\log{n})\)

Time complexity: \(O(n + k\log{n})\)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>

#define N 20
typedef struct node
{
	int *array;
	int count;	// Number of elements in the heap	
	int capacity;	// Size of the heap	
	int heap_type;	//0: Min heap or 1: Max heap
} *Heap;

Heap CreateHeap(int capacity, int heap_type)
{
	Heap h = (Heap)malloc(sizeof(struct node));
	h->heap_type = heap_type;
	h->count = 0;
	h->capacity = capacity;
	h->array = (int *)malloc(sizeof(int)*h->capacity);
	if (!h->array) return NULL;
	return h;
}

int Parent(Heap h, int i)
{
	if (i <= 0 || i >= h->count)
		return -1;
	return ((i - 1) / 2);
}

int LeftChild(Heap h, int i)
{
	int left = 2 * i + 1;
	if (left >= h->count) return -1;
	return left;
}

int RightChild(Heap h, int i)
{
	int right = 2 * i + 2;
	if (right >= h->count)
		return -1;
	return right;
}

int GetMaximum(Heap h)
{
	if (h->count == 0)
		return -1;
	return h->array[0];
}

void PercolateDown(Heap *h, int i) // Heapifying an element at location i
{
	int l, r, max, temp;
	l = LeftChild(*h, i);
	r = RightChild(*h, i);

	if (l != -1 && (*h)->array[l]>(*h)->array[i])
		max = l;
	else
		max = i;
	if (r != -1 && (*h)->array[r]>(*h)->array[max])
		max = r;
	if (max != i)
	{	// Swap h->array[i] and h->array[max];		
		temp = (*h)->array[i];
		(*h)->array[i] = (*h)->array[max];
		(*h)->array[max] = temp;
		PercolateDown(h, max);
	}

}

int DeleteMax(Heap *h)
{
	int data;
	if ((*h)->count == 0)
		return -1;
	data = (*h)->array[0];
	(*h)->array[0] = (*h)->array[(*h)->count - 1];
	(*h)->count--;
	PercolateDown(h, 0);
	return data;
}

void ResizeHeap(Heap *h)
{
	int i;
	int *array_old = (*h)->array;
	(*h)->array = (int *)malloc(sizeof(int)*(*h)->capacity * 2);
	/*	if(!(*h)->array)
	exit(-1);	*/
	for (i = 0; i<(*h)->capacity; i++)
		(*h)->array[i] = array_old[i];
	(*h)->capacity *= 2;
	free(array_old);
}


int Insert(Heap *h, int data)
{
	int i;
	if ((*h)->count == (*h)->capacity)
		ResizeHeap(h);
	(*h)->count++;	//increasing the heap size to hold this new item	
	i = (*h)->count - 1;
	while (i>0 && data > (*h)->array[(i - 1) / 2])
	{
		(*h)->array[i] = (*h)->array[(i - 1) / 2];
		i = (i - 1) / 2;
	}
	(*h)->array[i] = data;
}

void DestroyHeap(Heap *h)
{
	if (h == NULL) return;
	free((*h)->array);
	free(h);
	h = NULL;
}

void BuildHeap(Heap *h, int A[], int n)
{
	int i;
	if (h == NULL) return;
	while (n > (*h)->capacity)
		ResizeHeap(h);
	for (i = 0; i<n; i++)
		(*h)->array[i] = A[i];
	(*h)->count = n;

	for (i = (n - 1) / 2; i >= 0; i--)
	{
		PercolateDown(h, i);
	}
}


void HeapSort(int A[], int n)
{
	Heap h = CreateHeap(n, 1);
	int old_size, i, temp;
	BuildHeap(&h, A, n);
	old_size = h->count;
	for (i = n - 1; i >= 0; i--)
	{	//h->array[0] is the largest element		
		temp = h->array[0];
		h->array[0] = h->array[h->count - 1];
		h->array[h->count - 1] = temp;
		h->count--;
		PercolateDown(&h, 0);
	}
	h->count = old_size;

	for (i = 0; i<h->count; i++)
		A[i] = h->array[i];
}




void print_max(int A[], int n, int k)
{
	Heap h = CreateHeap(n, 1);
	BuildHeap(&h, A, n);
	while (k--)
		printf("%d \n", DeleteMax(&h));
}

int main()
{

	int tab[N], size, i, k;

	printf("Enter the number of elements in the array\n");
	scanf("%d", &size);

	printf("Enter %d integers\n", size);

	for (i = 0; i < size; i++)
		scanf("%d", &tab[i]);

	printf("Enter k\n");
	scanf("%d", &k);

	print_max(tab, size, k);

	getch();
	return 0;
}