【LeetCode】八、堆的使用：第K个最大元素 + 前K和高频单词

1、Java中的堆结构

• PriorityQueue类
• 取堆顶元素
• 删除堆顶元素
• 堆的元素个数
• 遍历堆

2、leetcode215：数组中的第K个最大元素

这题应该快排来解，这里用堆仅做练习。用堆实现的思路：将数组存入最大堆，k=1，找第一大的元素，则取堆顶元素，k=2，找第二大的元素，则删掉堆顶元素，取最新的堆顶元素，k=3，则删掉两次堆顶元素后，取新的堆顶元素

public class P215 {

    public static int getKMax(int[] array, int k) {
        if (array == null || array.length == 0 || k < 1){
            return Integer.MIN_VALUE;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int i : array) {
            maxHeap.add(i);
        }
        while (k > 1) {
            // 删掉前面第k-1大的所有元素
            maxHeap.poll();
            k--;
        }
        // 取出删掉后新的堆顶元素，即第K大的元素
        return maxHeap.peek();
    }
}

测试：

public class P215 {
    public static void main(String[] args) {
        int[] array = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(getKMax(array, 4));
    }
}

3、leetcode692：前K个高频单词

本质是个统计次数的问题，自然想到哈希表结构，可用HashMap，统计完后，前k个、第K个，则可考虑最大堆。不过，题中要求次数相等时，按照字母排序，因此，要自定义比较器的实现：先比次数，次数相等再按字母排序

如果要用最小堆实现：应该将值最小的元素往堆顶放、同等次数的把字母靠后的往堆顶放

然后，限制最小堆里元素的个数为k个，当超出k时，剔除堆顶元素，因为堆顶元素最小，我要的是前K大的。遍历map完成后，从堆中循环取出堆顶数据，此时得到的顺序是从小到大的，再反转下，即可return

这里用最小堆和最小堆分别来解决：

public class P692 {

    /**
     * 统计每个单词出现的数量
     */
    public static HashMap<String, Integer> stats(String[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        HashMap<String, Integer> statsMap = new HashMap<>();
        for (String str : array) {
            // 判断下是否包含这个key，不要直接map.get(str) + 1
            // 没这个key时，get返回null，null + 1会空指针
            if (!statsMap.containsKey(str)) {
                statsMap.put(str, 1);
            } else {
                statsMap.put(str, statsMap.get(str) + 1);
            }
        }
        return statsMap;
    }

    /**
     * 用最小堆解题
     */
    public static List<String> calcKMaxByMinHeap(HashMap<String, Integer> map, Integer k) {
        PriorityQueue<StrInfo> minHeap = new PriorityQueue<>(new Comparator<StrInfo>() {
            @Override
            public int compare(StrInfo o1, StrInfo o2) {
                if (!o1.count.equals(o2.count)) {
                    return o1.count - o2.count;
                } else {
                    return o2.str.compareTo(o1.str);
                }
            }
        });
        map.forEach((str, count) -> {
            // 将每一条统计数据入堆，入堆时会按照上面的比较规则做成最小堆
            minHeap.add(new StrInfo(str, count));
            // 入堆后如果元素数量超过了k，扔掉堆顶元素
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        });

        // 将堆中的k个单词放入结果集
        List<String> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll().str);
        }
        // 结果倒转，按题目要求的顺序return
        Collections.reverse(result);
        return result;
    }

    /**
     * 用最大堆解题
     */
    public static List<String> calcKMaxByMaxHeap(HashMap<String, Integer> map, Integer k) {
        PriorityQueue<StrInfo> maxHeap = new PriorityQueue<>(new Comparator<StrInfo>() {
            @Override
            public int compare(StrInfo o1, StrInfo o2) {
                if (!o1.count.equals(o2.count)) {
                    return o2.count - o1.count;
                } else {
                    return o1.str.compareTo(o2.str);
                }
            }
        });
        // 将每一条统计数据入堆，入堆时会按照上面的比较规则做成最大堆
        map.forEach((str, count) -> {
            maxHeap.add(new StrInfo(str, count));
        });
        // 取前k个堆顶元素即为前K个高频单词
        List<String> result = new ArrayList<>();
        while (k > 0) {
            result.add(maxHeap.poll().str);
            k--;
        }
        return result;

    }
}


class StrInfo {
    String str;
    Integer count;

    public StrInfo(String str, Integer count) {
        this.str = str;
        this.count = count;
    }
}

测试：

public class P692 {
    public static void main(String[] args) {
        String[] array = {"i", "love", "leetcode", "i", "love", "coding"};
        System.out.println(calcKMaxByMinHeap(stats(array), 2));
    }
}