LintCode 559 - Trie Service

https://www.lintcode.com/problem/trie-service/
Build tries from a list of pairs. Save top 10 for each node.

Example
Given a list of

<"abc", 2>
<"ac", 4>
<"ab", 9>

Return <a[9,4,2]<b[9,2]<c[2]<>>c[4]<>>>, and denote the following tree structure:

         Root
         / 
       a(9,4,2)
      /    \
    b(9,2) c(4)
   /
 c(2)

https://blog.csdn.net/roufoo/article/details/81669842
class TrieService {
private:
    TrieNode* root;

public:
    TrieService() {
        root = new TrieNode();
    }

    TrieNode* getRoot() {
        // Return root of trie root, and
        // lintcode will print the tree struct.
        return root;
    }

    //important code   
    void insert(string& word, int frequency) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); ++i) {
            if (p->children.find(word[i]) == p->children.end()) {
                p->children[word[i]] = new TrieNode();
            }
            p = p->children[word[i]];
            helper(p->top10, frequency);
        }
    }


    //insert to the right place, top10 is sorted from large to small
    void helper(vector<int>& top10, int freq) {
        top10.push_back(freq);
        int top10Size = top10.size();
        if (top10Size == 1) return;

        //start from top10Size - 2 as top10Size - 1 is already freq
        for (int i = top10Size - 2; i >= 0; --i) {
            if (top10[i] < top10[i + 1]) {
                int temp = top10[i];
                top10[i] = top10[i + 1];
                top10[i + 1] = temp;
            } else {
                break;
            }
        }

        if (top10Size > 10) top10.pop_back();
    }
}
https://github.com/zxqiu/leetcode-lintcode/blob/master/system%20design/Trie_Service.java
解：
把输入的单词放进树中，在放入频率的时候按从大到小顺序插入top10 List中即可。
如果top10 List大小大于10，则删掉最后一个元素。
*/



/**
 * Definition of TrieNode:
 * public class TrieNode {
 *     public NavigableMap<Character, TrieNode> children;
 *     public List<Integer> top10;
 *     public TrieNode() {
 *         children = new TreeMap<Character, TrieNode>();
 *         top10 = new ArrayList<Integer>();
 *     }
 * }
 */
public class TrieService {

    private TrieNode root = null;

    public TrieService() {
        root = new TrieNode();
    }

    public TrieNode getRoot() {
        // Return root of trie root, and
        // lintcode will print the tree struct.
        return root;
    }

    // @param word a string
    // @param frequency an integer
    public void insert(String word, int frequency) {
        TrieNode iter = root;
     
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!iter.children.containsKey(c)) {
                iter.children.put(c, new TrieNode());
            }
         
            TrieNode node = iter.children.get(c);
            int insert_idx;
            for (insert_idx = 0; insert_idx < node.top10.size(); insert_idx++) {
                if (node.top10.get(insert_idx) <= frequency) {
                    break;
                }
            }
         
            node.top10.add(insert_idx, frequency);
         
            if (node.top10.size() == 11) {
                node.top10.remove(10);
            }
         
            iter = node;
        }
    }