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()

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;
    }
};