认识堆

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型：

小顶堆：任意节点的值 <= 其子节点的值
大顶堆：任意节点的值 >= 其子节点的值

堆作为完全二叉树的一个特例，具有以下特性：

最底层节点靠左填充，其他层的节点都被填满。
我们将二叉树的根节点称为堆顶，将底层最靠右的节点称为堆底
对于大顶堆（小顶堆），堆顶元素即根节点的值是最大（最小）的

实际上，堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将优先队列和堆看作等价的数据结构。
Java中堆的一些操作使用优先队列来实现，具体代码如下所示：

// 初始化小顶堆
Queue<Integer> minHeap = new PriorityQueue<>();
// 初始化大顶堆（使用 lambda 表达式修改 Comparator 即可）
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
/* 元素入堆 */
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(5);
maxHeap.offer(4);
/* 获取堆顶元素 */
int peek = maxHeap.peek(); // 5
/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
peek = maxHeap.poll(); // 5
peek = maxHeap.poll(); // 4
peek = maxHeap.poll(); // 3
peek = maxHeap.poll(); // 2
peek = maxHeap.poll(); // 1
/* 获取堆大小 */
int size = maxHeap.size();
/* 判断堆是否为空 */
boolean isEmpty = maxHeap.isEmpty();
/* 输入列表并建堆 */
minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4));

要注意，堆的逻辑结构是一棵完全二叉树，但是其物理存储则是采用数组来存储。

Top-k问题

给定一个长度为 n 的无序数组 nums ，请返回数组中最大的 k 个元素。

初始化一个小顶堆，其堆顶元素最小
先将数组的前 k 个元素依次入堆
从 k + 1 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆
遍历完成后，堆中保存的就是最大的 k 个元素

Queue<Integer> topKHeap(int[] nums, int k) {
    // 初始化小顶堆
    Queue<Integer> heap = new PriorityQueue<Integer>();
    // 将数组的前 k 个元素入堆
    for (int i = 0; i < k; i++) {
        heap.offer(nums[i]);
    }
    // 从第 k+1 个元素开始，保持堆的长度为 k
    for (int i = k; i < nums.length; i++) {
        // 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if (nums[i] > heap.peek()) {
            heap.poll();
            heap.offer(nums[i]);
        }
    }
    return heap;
}

数组中的第K个最大元素

力扣题目链接
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

优先队列（小顶堆），里面保存 K 个数字
比堆顶元素大，就存进去，到最后是最大的 K 个数字
则堆顶是第 K 个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for (int num : nums) {
            if (queue.size() < k) {
                queue.offer(num);
            } else if (num > queue.peek()) {
                queue.poll();
                queue.offer(num);
            }
        }
        return queue.peek();
    }
}

前K个高频元素

力扣题目链接
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

map 存数字以及出现的频率
根据 map.keySet() 建立小顶堆（重写排序逻辑）

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (int num : map.keySet()) {
            if (queue.size() < k) {
                queue.offer(num);
            } else if (map.get(num) > map.get(queue.peek())) {
                queue.poll();
                queue.offer(num);
            }
        }
        int[] ans = new int[k];
        int i = 0;
        while (queue.size() != 0) {
            ans[i] = queue.poll();
            i++;
        }
        return ans;
    }
}