# Top K Frequent Words II

`Data Stream`, `HashMap`, `TreeSet`

### Description

Find top\_k \_frequent words in realtime data stream.

Implement three methods for Topk Class:

1. `TopK(k)`. The constructor.
2. `add(word)`. Add a new word.
3. `topk()`. Get the current top \_k \_frequent words.

> If two words have the same frequency, rank them by alphabet.

### Example

```
TopK(2)
add("lint")
add("code")
add("code")
topk()
>> ["code", "lint"]
```

## Solution

#### [Jiuzhang's Solution](https://www.lintcode.com/problem/top-k-frequent-words-ii/solution): HashMap + TreeSet

**注意：**

1. 这里add()时，如果TreeSet中存在这个word，要先删去该word，更新HashMap中word对应的count，再将其加入TreeSet，这样就可以利用更新过的count来排序了。否则TreeSet中已经存在的word没法改变其排序。
2. 这里的TreeSet用的是根据words count来排序，并且count越高排序越靠前，因此可以想成（用PriorityQueue）的Max-Heap，与PriorityQueue相对应的，这里TreeSet因为可以直接用`pollLast()`删去last(highest) element，也就是移除最小的word count，因此这里可以使用Max-Heap的思想而不是Min-Heap。

```java
/**
* This reference program is provided by @jiuzhang.com
* Copyright is reserved. Please indicate the source for forwarding
*/

import java.util.NavigableSet;

public class TopK {
    private Map<String, Integer> words = null;
    private NavigableSet<String> topk = null;
    private int k;

    private Comparator<String> myComparator = new Comparator<String>() {
        public int compare(String left, String right) {
            if (left.equals(right))
                return 0;

            int left_count = words.get(left);
            int right_count = words.get(right);
            if (left_count != right_count) {
                return right_count - left_count;
            }
            return left.compareTo(right);
        }
    };

    public TopK(int k) {
        // initialize your data structure here
        this.k = k;
        words = new HashMap<String, Integer>();
        topk = new TreeSet<String>(myComparator);
    }

    public void add(String word) {
        // Write your code here
        if (words.containsKey(word)) {
            if (topk.contains(word))
                topk.remove(word);
            words.put(word, words.get(word) + 1);
        } else {
            words.put(word, 1);
        }

        topk.add(word);
        if (topk.size() > k) {
            topk.pollLast();
        }
    }

    public List<String> topk() {
        // Write your code here
        List<String> results = new ArrayList<String>();
        Iterator it = topk.iterator();
        while(it.hasNext()) {
             String str = (String)it.next();
             results.add(str);
        }
        return results;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/heap/top-k-frequent-words-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.