算法笔记之堆求取前N个元素

堆（heap）是一种特殊的数据结构，它通常被看作是一棵树的数组对象，堆总是一颗完全二叉树。

堆分为最大堆和最小堆，在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。

堆经常使用的场景：

• 构建优先队列
• 堆排序
• 快速找出一个集合中的前N大（小）的值

Leetcode347. 前 K 个高频元素

问题概述：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

解题思路：相当与找出一个集合中前 k 大的值。

Java语言中的优先队列 PriorityQueue 就是使用堆实现的，我们可以使用优先队列解决本题。

Java代码：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            numMap.put(nums[i], numMap.getOrDefault(nums[i], 0) + 1);
        }

        // 优先队列，自定义排序方式
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for(Map.Entry<Integer, Integer> entry : numMap.entrySet()) {
            if(queue.size() < k) {
                queue.offer(new int[] {entry.getKey(), entry.getValue()});
            } else {
                int min = queue.peek()[1];
                if(min < entry.getValue()) {
                    queue.poll();
                    queue.offer(new int[] {entry.getKey(), entry.getValue()});
                }
            }
        }

        int[] result = new int[k];
        for(int i = 0; i < k; i++) {
            result[i] = queue.poll()[0];
        }
        return result;
    }
}

Leetcode 692. 前K个高频单词

问题概述：给一非空的单词列表，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

解题思路：和上题类似，只是排序方式发生了变化。

Java代码：

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> frequentMap = new HashMap<String, Integer>();
        for(int i = 0; i < words.length; i++) {
            frequentMap.put(words[i], frequentMap.getOrDefault(words[i], 0) + 1);
        }
        PriorityQueue<String> queue = new PriorityQueue<String>(
            new Comparator<String>() {
                @Override
                public int compare(String a1, String a2) {
                    int b = frequentMap.get(a1) - frequentMap.get(a2);
                    if(b != 0) {
                        return b;
                    } else {
                        return -a1.compareTo(a2);
                    }
                }
            }
        );
        for(Map.Entry<String, Integer> entry : frequentMap.entrySet()) {
            queue.offer(entry.getKey());
            if(queue.size() > k) {
                queue.poll();
            }  
        }

        List<String> result = new ArrayList<String>();
        while(!queue.isEmpty()) {
            result.add(queue.poll());
        }
        Collections.reverse(result);