# Top k Largest Numbers II

`Data Stream`, `Priority Queue`, `Heap`

**Medium**

## Question

> 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.
>
> Example

**Example1**

```
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]
```

**Example2**

```
Input: 
s = new Solution(1);
s.add(3)
s.add(10)
s.topk()
s.topk()

Output: 
[10]
[10]

Explanation:
s = new Solution(1);
>> create a new data structure, and k = 1.
s.add(3)
s.add(10)
s.topk()
>> return [10]
s.topk()
>> return [10]
```

## Analysis

与top k问题1类似，不太一样的一点在于动态添加，使用min heap来实现，能够比较好地通过更新min heap来记录top k。

当添加的元素数目在1 \~ k时，直接插入这一元素到min heap中；\
当添加的元素数目超出k时，对于新添加的元素，需要与min heap的根进行比较，如果比minheap.peek()大，那么便删除根，添加该新元素。

## Solution

### Min-Heap + iterator()

```java
public class Solution {
    private PriorityQueue<Integer> minheap;
    private int maxSize;

    public Solution(int k) {
        minheap = new PriorityQueue<Integer>();
        maxSize = k;
    }

    public void add(int num) {
        if (minheap.size() < maxSize) {
            minheap.offer(num);
        } else {
            if (num > minheap.peek()) {
                minheap.poll();
                minheap.offer(num);
            }
        }

    }

    public List<Integer> topk() {
        Iterator iter = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (iter.hasNext()) {
            result.add((Integer) iter.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
};
```