Implement a data structure, provide two interfaces:

1. add(number) . Add a new number in the data structure.
2. topk() . Return the top k largest numbers in this data structure. k is given when we create the data structure.

Have you met this question in a real interview?

Yes

Example

s = new Solution(3);

>
>
 create a new data structure.
s.add(3)
s.add(10)
s.topk()

>
>
 return [10, 3]
s.add(1000)
s.add(-99)
s.topk()

>
>
 return [1000, 10, 3]
s.add(4)
s.topk()

>
>
 return [1000, 10, 4]
s.add(100)
s.topk()

>
>
 return [1000, 100, 10]

class Solution {
public:
    Solution(int k) {
        // initialize your data structure here.
        this->k = k;
    }

    void add(int num) {
        // Write your code here
        q.push(num);
        if (q.size() > k) {
            q.pop();
        }
    }

    vector<int> topk() {
        // Write your code here
        vector<int> res;
        int size = q.size() < k ? q.size() : k;
        for (int i = 0; i < size; ++i) {
            res.push_back(q.top());
            q.pop();
        }
        for (int num : res) {
            q.push(num);
        }
        reverse(res.begin(), res.end());
        return res;
    }

private:
    int k;
    std::priority_queue<int, vector<int>, std::greater<int>> q;
};