[Solved] Kth Maximum element of Max-Heap Contest Problem

Kth Maximum element of Max-Heap: Given a max heap array mHeap of positive integers of size N and a positive integer k. The task is to find the k_th maximum element of the heap.

Kth Maximum element of Max-Heap Contest Problem

Input:
First line of input contains T, denoting the number of test cases. For each test case there will be two lines. The first line caontains N(size of the heap) and k. The second line contains N space separated integers.

Output:
For each testcase print the required answer i.e. kth maximum element.

Constraints:
1 <= T <= 100
1 <= N <= 1000
1 <= k <= N
1 <= mHeap[i] <= 1000

Example:
Input:
2
7 3
50 40 30 35 38 20 25
9 6
60 55 57 54 53 50 52 51 49

Output:
38
52

Explanation
Testcase 1: The given array 40 38 35 30 20 25 of max heap is as shown:
                                              50(0)    
                                               /     \
                                         40(1)  38(2)
                                         /     \
                                   35(3)   30(4)
                                 /      \
                             20(5)  25(6)

Now the top 3 maximum elements are 50 40 38, so the 3rd maximum element will be 38.

Solution

#include <bits/stdc++.h> 
using namespace std; 


struct Heap { 
	vector<long long> v; 
	int n; // Size of the heap 

	Heap(int i = 0) 
		: n(i) 
	{ 
		v = vector<long long>(n); 
	} 
}; 

// Returns the index of 
// the left child node 
long long left(long long i) 
{ 
	return 2 * i + 1; 
} 

// Returns the index of 
// the right child node 
 long long right(long long i) 
{ 
	return 2 * i + 2; 
} 

long long findKthLargest(Heap &h, int k) 
{ 
	// Create a Priority Queue 
	priority_queue<pair<long long, long long>, 
				vector<pair<long long, long long> >> 
				  
		p; 

	// Insert root into the priority queue 
	p.push(make_pair(h.v[0], 0)); 

	for (int i = 0; i < k - 1; ++i) { 
		long long j = p.top().second; 
		p.pop(); 
		long long l = left(j), r = right(j); 
		if (l < h.n) 
			p.push(make_pair(h.v[l], l)); 
		if (r < h.n) 
			p.push(make_pair(h.v[r], r)); 
	} 

	return p.top().first; 
} 

int main() 
{ 
    int t;
	cin >> t;
	
	while(t--)
	{
	    int n, k;
	    
	    cin>>n>>k;
	    
	    Heap h(n);
	    vector<long long> vec;
	    for(long long i = 0; i < n; i++)
	       {
	           long long x;
	           cin>>x;
	           vec.push_back(x);
	       }
	       
	       h.v = vec;
	       
	       cout << findKthLargest(h, k) << endl;
	       
	}
	 
	return 0; 
} 

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
 public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int T = Integer.parseInt(st.nextToken());
        while (T-- > 0) {
            executeOneTestCase(bf);
        }
    }

    private static void executeOneTestCase(BufferedReader bf) throws IOException {
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int size = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        Integer[] arr = new Integer[size];
        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, Collections.reverseOrder());
        System.out.println(arr[K - 1]);


    }
}

Happy Learning – If you require any further information, feel free to contact me.