思路:
小顶堆如图所示:根节点始终是这颗树里面最小的,开始构建一个k个节点的树,然后结合k+1,k+2,k+3...个节点和小顶堆里面的根节点(即:最小的节点)进行比较,如果第K+1个节点比根节点大,那么弹出小顶堆的根节点,然后将第k+1个节点塞入小顶堆中,让小顶堆重新构建排列,输出后的树,根节点仍然是最小的,所以以此类推
PriorityQueue(优先队列),一个基于优先级堆的无界优先级队列。
实际上是一个堆(不指定Comparator时默认为最小堆),通过传入自定义的Comparator函数可以实现大顶堆。

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小顶堆,默认容量为11
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大顶堆,容量11
    @Override
    public int compare(Integer i1,Integer i2){
        return i2-i1;
    }
});

图片说明
注意:其中根节点的左右孩子顺序 根据比较器来进行排列的 可以看PriorityQueue的原理,如此图10的左右节点 是无序的,但每次PriorityQueue弹出元素后,会重建最小堆,那么新的最小堆的根节点仍然是最小的
remove()和poll()
remove()和poll()方法的语义也完全相同,都是获取并删除队首元素,区别是当方法失败时前者抛出异常,后者返回null。由于删除操作会改变队列的结构,为维护小顶堆的性质,需要进行必要的调整。
图片说明
图片说明

add()和offer()
add(E e)和offer(E e)的语义相同,都是向优先队列中插入元素,只是Queue接口规定二者对插入失败时的处理不同,前者在插入失败时抛出异常,后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。
图片说明

题解:

import java.util.*;


public class Solution {
    /**
     * 题意要求是TopK问题,时间复杂度达到O(NlogK),并且相同大小要按字典排序,
     * 所以排序方法应该是堆排序或者快速选择排序。
     * 这里排序使用小顶堆,按值排序时是从小到大。当值相同时,比较str,这里重写堆节点的比较方法,
     * 值相同时,str字典序大的先入堆。
     * 最后,排序好的小顶堆输出k个数到结果集,结果集数组从尾部开始填充,
     * 这样小顶堆的数据刚好逆序,在结果集里的表现就是 按值排序是升序,值相同是字典小的在数组前面。
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {

        if(strings==null || strings.length==0){
            return null;
        }

        HashMap<String,Integer> map = new HashMap();
        for(String s : strings){
            //初始化 数组中每个字符串默认出现一次
            map.put(s,map.getOrDefault(s,0)+1);
        }

        // 优先队列,实现小顶堆,输出到结果集就是堆的逆序,即倒序输出小顶堆,即大顶堆
        //https://blog.csdn.net/wufaliang003/article/details/82940218参考最小堆的思想
        //https://blog.csdn.net/luzhensmart/article/details/119922081
        PriorityQueue<Node> minHeap = new PriorityQueue();
        for(Map.Entry<String,Integer> entrySet : map.entrySet()){
            Node node = new Node(entrySet.getKey(),entrySet.getValue());
            //先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。
            //这里为什么不是=k 是因为第一次for循环map minHeap.size()=0 然后=1 = 2 =3...=k 多出了一次0 所以这里还是相当于往里添加了k个元素
            if(minHeap.size() < k){
                minHeap.add(node);
            }else{
                // 堆中元素等于 k 个时
                // 当 node的值大于栈顶元素,或者值相同时且node的字典小于栈顶元素 时(最小堆构建规则,就是如此)
                //这相当于上一个条件:先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。
                //接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,
                //以保证堆内的k个元素,总是当前最大的k个元素。
                if(minHeap.peek().compareTo(node) < 0){
                    minHeap.poll();
                    minHeap.add(node);
                }
            }
        }

        //声明一一个二维数组,用于存储3个一维数组,每一个一维数据存2个数
        String[][] result = new String[k][2];
        //正序弹出小顶堆上面的元素,数组逆序输出
        for(int i=k-1;i>=0;i--){
            Node node = minHeap.poll();
            result[i][0] = node.name;
            result[i][1] = String.valueOf(node.count); 
        }
        return result;
    }

    class Node implements Comparable<Node>{

        //对应上面Map里的key
        String name;
        //对应上面Map里的value
        int count;

        public Node(String name,int count){
            this.name = name;
            this.count = count;
        }

        @Override
        public int compareTo(Node node){
            //正常是通过Node对象里的count来比较大小的
            if(this.count > node.count){
                return 1;
            }else if(this.count < node.count){
                return -1;
            }else{
                //比如["2","2","1","1"]的情况 数组中字符串2出现2次 字符串1出现2次 这时候要求按字典顺序输出["1","2"]、["2","2"]1出现2次 2出现2次
                //此时使用原生的比较器 用2个Node对象的string进行字典顺序比较
                //上面的2个条件比较对象是堆顶的元素 被比较对象是要是否加入替代堆顶最小元素的元素 用的是count大小做比较
                //但此时Node值相同,应该比较的是要加入的node的name字典值,小于栈顶元素 才会重新进行构建最小堆 应该反过来比较
                //如果按照上面正常的逻辑 ASCII小的 反而弹出了 重新构建堆了,所以应该反向逻辑
                return node.name.compareTo(this.name);
            }
        }
    }
}