堆（Heap）

基本介绍

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

小顶堆 min heap - 任意节点的值 ≤ 其子节点的值。
大顶堆 max 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));

常见应用

优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为 O(log⁡ n) ，而建队操作为 O(n) ，这些操作都非常高效。
堆排序：给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数据。
获取最大的 k 个元素：这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻作为微博热搜，选取销量前 10 的商品等。

Top-k问题

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

对于堆，我们可以先初始化一个小顶堆，将数组的前k个元素入堆，对于后面的元素，如果大于堆顶的元素，那么就将堆顶元素出堆，将当前元素入堆。遍历完成后，堆中保存的就是最大的k个元素。

/* 基于堆查找数组中最大的 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;
}

leetcode 相关问题

215. 数组中的第K个最大元素

直接使用上面的方法，或者直接调用Arrays.sort对数组进行排序，这里不详细写。

347. 前 K 个高频元素

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

遇到top-k问题，可以想到用堆来解决，但是这道题还涉及到元素出现的次数，可以用hashmap来记录元素出现次数。

public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int j : nums) {
            if (hashMap.containsKey(j)) {
                hashMap.put(j, hashMap.get(j) + 1);
            } else {
                hashMap.put(j, 1);
            }
        }
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            int num = entry.getValue();
            if (priorityQueue.size() == k) {
                if (num > priorityQueue.peek()[1]) {
                    priorityQueue.poll();
                    priorityQueue.offer(new int[]{entry.getKey(), num});
                }
            } else {
                priorityQueue.offer(new int[]{entry.getKey(), num});
            }
        }
        int[] res = new int[priorityQueue.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = priorityQueue.poll()[0];
        }
        return res;
    }

355. 设计推特

List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。设计到了top-k问题，可以考虑用一个static的优先级队列维护最近发送的帖子，时间也可以使用一个静态变量，每次发帖加1来模拟发帖时间。具体实现这里不详细展开。
373. 查找和最小的 K 对数字