PriorityQueue (large root heap / small root heap /topk problem)

        PriorityQueue It's from JDK1.5 Start to provide new data structure interface , It's a very high priority queue based on priority heap . Priority queue is another kind of queue different from FIFO queue . Each time the element with the highest priority is removed from the queue .

         By default ,PriorityQueue yes Small cap pile , As the code shows

public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        queue.offer(6);
        while (!queue.isEmpty()){
            System.out.print(queue.poll() + " ");
        }
    }

         Output results ：

         We can also construct it in the following ways Big pile top ：

public static void main(String[] args) {
  PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);// Descending 
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        queue.offer(6);
        while (!queue.isEmpty()){
            System.out.print(queue.poll() + " ");
        }
    }

        Output results ：

         Top K problem , Power button 347 Heli button 692：

Power button 347： Give you an array of integers  nums  And an integer  k , Please return to the frequency before  k  High element . You can press   In any order   Return to the answer .

Example ：

 Input : nums = [1,1,1,2,2,3], k = 2
 Output : [1,2]

        The code is as follows ： Pay attention to the construction of small top pile (o1,o2)-> o1.getValue() - o2.getValue() Don't omit .

public int[] topKFrequent(int[] nums, int k) {
        //key Element value ,value For frequency of occurrence 
        HashMap<Integer,Integer> map = new HashMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> queue 
        = new PriorityQueue<>((o1,o2)-> o1.getValue() - o2.getValue());
        int[] res = new int[k];
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            queue.offer(entry);
            if(queue.size() > k){
                queue.poll();
            }
        }
        // What remains is the most frequent 
        for(int i = 0; i < k; i++){
            Map.Entry<Integer, Integer> poll = queue.poll();
            res[i] = poll.getKey();
        }
        return res;

Power button 692： Given a list of words  words  And an integer k , Return to the former  k  The most frequently used word . The answers returned should be sorted by word frequency from high to low . If different words have the same frequency , Sort in dictionary order .

Example ：

Input : words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output : ["i", "love"]
analysis : "i" and "love" For the two words that appear most frequently , Are all 2 Time . Be careful , In alphabetical order "i" stay "love" Before .

        This question is a little more difficult than the last one , Because when two words appear the same number of times, we should also consider sorting by dictionary , The second is that the answers need to be sorted from top to bottom , This is mainly reflected in the priority queue PriorityQueue On the structure of . The code is as follows ：

public List<String> topKFrequent(String[] words, int k) {
        List<String> res = new ArrayList<>();
        //key For the elements ,value For frequency of occurrence 
        HashMap<String,Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0) + 1);
        }
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(
                ((o1, o2) -> {
                    if(o1.getValue() == o2.getValue()){
                        return o2.getKey().compareTo(o1.getKey());
                    }
                    return o1.getValue() - o2.getValue();
                })
        );
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            queue.offer(entry);
            if(queue.size() > k){
                queue.poll();
            }
        }
        for(int i = 0; i < k; i++){
            res.add(queue.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }

        Be careful o2.getKey().compareTo(o1.getKey()) Is in reverse order of the dictionary , Why do that , Because we use a small top pile here , So every time poll What comes out is the smallest frequency element , Last need reverse once , In order to cooperate with this , So when we construct the priority queue, we use the reverse order of the dictionary .