Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:


	KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
	int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.


&nbsp;
Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8


&nbsp;
Constraints:


	1 &lt;= k &lt;= 104
	0 &lt;= nums.length &lt;= 104
	-104 &lt;= nums[i] &lt;= 104
	-104 &lt;= val &lt;= 104
	At most 104 calls will be made to add.
	It is guaranteed that there will be at least k elements in the array when you search for the kth element.


class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.hp = []
        for x in nums:
            self.add(x)

        return None

    def add(self, val: int) -> int:
        heapq.heappush(self.hp, (val))
        if len(self.hp) > self.k:
            heapq.heappop(self.hp)

        return self.get_kth_largest()

    def get_kth_largest(self):
        return self.hp[0]
class KthLargest {
    PriorityQueue<Integer> queue=new PriorityQueue();
    int k=0;
    public KthLargest(int k, int[] nums) {
        this.k=k;
        for(int i:nums)
            add(i);
    }
    
    public int add(int val) {
        if(k>queue.size())
            queue.add(val);
        else
            if(val>queue.peek())
            {
                queue.poll();
                queue.add(val);
            }
        return queue.peek();
    }
}
class KthLargest {
    
    int k;
    priority_queue<int, vector<int>, greater<int>> minheap;
    int n;
    
public:
    KthLargest(int k, vector<int>& nums) {
        this->k=k;
        this->n=nums.size();
        
//         push the initial elements in the heap
        for(auto x : nums){
            minheap.push(x);
        }
        
//         if the no. of elements are greater than k then remove them
        while(n>k){
            minheap.pop();
            n--;
        }
    }    
    
    int add(int val) {
        
//         if heap is empty or no. of elements are less than k then add the input
        if(minheap.empty() || n<k){
            minheap.push(val);
            this->n=n+1;
        }
//         else compare it with top
        else{
            int minn=minheap.top();
//             if the input is greater than top
            if(minn<val){
                minheap.pop();
                minheap.push(val);
            }
        }
//         at any point of time top of the heap is required ans
        return minheap.top();
        
        
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */
var KthLargest = function(k, nums) {
    // sort ascending because I am familiar with it
    // when applying my binary search algorithm
    this.nums = nums.sort((a,b) => a - b);    
    this.k = k;    
};

KthLargest.prototype.add = function(val) {
    // search a place to push val
    // using binary search
    let left = 0; right = this.nums.length - 1;
    while (left < right) {
        let mid = left + Math.floor((right + 1 - left)/2);
        
        if (val < this.nums[mid]) {
            right = mid - 1;
        } else {
            left = mid
        }
    }    
    
    // push val into the nums
    this.nums.splice(left+(this.nums[left] < val ? 1 : 0), 0, val);  

    // because our nums is sorted
    // so kth largest element is easy to be returned
    return this.nums[this.nums.length-this.k]
};
Kth Largest Element in a Stream