> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/heap/703.-kth-largest-element-in-a-stream.md).

# 703. Kth Largest Element in a Stream

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

Your `KthLargest` class will have a constructor which accepts an integer `k` and an integer array `nums`, which contains initial elements from the stream. For each call to the method `KthLargest.add`, return the element representing the kth largest element in the stream.

**Example:**

```cpp
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8
```

**Note:**\
You may assume that `nums`' length ≥ `k-1` and `k` ≥ 1.

```cpp
class KthLargest {
public:
    KthLargest(int k, vector<int>& nums) : cap(k) {
        for (const int& num : nums) {
            pq.push(num);
            if (pq.size() > cap) pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if (pq.size() > cap) pq.pop();
        return pq.top();
    }
private:
    priority_queue<int, vector<int>, greater<int> > pq;
    int cap;
};
```