TopN问题堆排序求解

1. 统计各个字符出现次数，使用Map
2. 创建初始堆(大顶堆)，定义出现次数大的字符串较大，出现次数相同是自然序较前的串较大
3. 依次去K个堆顶元素并调整堆

import java.util.*;


public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    public String[][] topKstrings (String[] strings, int k) {
        if(null == strings || strings.length == 0) {
            return new String[0][];
        }

        String[][] result = new String[k][];
        // 统计各个字符串出现次数
        Map<String,Integer> cntMap = new HashMap();
        for(String s : strings) {
            cntMap.put(s, cntMap.getOrDefault(s, 0)+1);
        }

        // 创建初始堆 大顶堆
        Node[] heapArr = new Node[cntMap.size()+1];
        int idx = 0;
        for(Map.Entry<String,Integer> entry : cntMap.entrySet()) {
            Node node = this.new Node(entry.getKey(), entry.getValue());
            heapArr[++idx] = node;
        }
        // 调整初始堆
        for(int i = idx/2; i > 0; --i) {
            shift(heapArr, i, heapArr.length);
        }

        // 取前K个
        int limit = heapArr.length-1;
        for(int i = 1; i <= k && i <= limit; ++i) {
            String[] r = new String[]{heapArr[1].val, String.valueOf(heapArr[1].cnt)};
            result[i-1] = r;

            Node temp = heapArr[1];
            heapArr[1] = heapArr[limit];
            heapArr[limit] = temp;
            --limit;

            // 调整堆
            shift(heapArr, 1, limit+1);
        }
        return result;
    }

    // 堆调整方法
    private void shift(Node[] heapArr, int startIdx, int endIdx) {
        int childIdx = 2 * startIdx;
        if(childIdx+1 < endIdx && heapArr[childIdx+1].compareTo(heapArr[childIdx]) > 0) {
            childIdx = childIdx + 1;
        }

        if(childIdx < endIdx && heapArr[childIdx].compareTo(heapArr[startIdx]) > 0) {
            Node temp = heapArr[childIdx];
            heapArr[childIdx] = heapArr[startIdx];
            heapArr[startIdx] = temp;
            shift(heapArr, childIdx, endIdx);
        }
    }

    // 堆结点定义
    class Node implements Comparable<Node> {
        String val;
        int cnt;
        Node() {}
        Node(String val, int cnt) {
            this.val = val;
            this.cnt = cnt;
        }

        //定义比较方法: cnt 大的大， cnt相同时，val自然序小的大
        public int compareTo(Node node) {
            if(this.cnt != node.cnt) {
                return this.cnt - node.cnt;
            } else {
                return -this.val.compareTo(node.val);
            }
        }
    }
}