前言

今天，我们来讨论一个非常实用的数据结构——二叉堆（Binary Heap，简称：堆），它最主要的应用场景有 堆排序 & 优先队列 & Top K & 最大索引堆。与堆相关算法题目基本属于中等难度，在算法面试中也比较常见，建议应试者着重学习；
在这篇文章里，我将梳理堆的 基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

系列文章

延伸文章

算法面试题 | 高楼丢鸡蛋（源自谷歌面试题）

1. 基本概念

逻辑结构

二叉堆（Binary Heap） 是一种特殊的完全二叉树，即：每个节点都大于等于（或者小于等于）子节点。需要注意的是，兄弟节点的相对大小是不重要的。

具体来说，如果每个节点都大于等于子节点，这种堆称为 大顶堆 / 最大堆；如果每个节点都小于等于子节点，这种堆称为 小顶堆 / 最小堆。

物理结构

树可以采用数组 & 链表两种存储方式，对于二叉堆（完全二叉树）来说，数组存储方式是空间利用率最高的存储方式。因此通常来说，二叉堆是基于数组的数据结构。

2. 堆的基本操作

这一节，我们先来讨论堆的三个基本操作 —— 上浮 & 下沉 & 建堆，这三个操作的目的其实都是堆化（Heapify）。建堆的作用是把一组数据转换为满足堆性质的数据结构，而上浮和下沉的作用是在堆结构变化之后，适当地调整节点使其重新满足堆的性质。

提示： 为了专注于讨论二叉堆的相关内容，在这一节里我们不考虑泛型，同时以大顶堆为例子。

2.1 上浮（添加元素）

往堆里添加元素时，需要执行上浮操作，具体步骤如下：

1、新元素放在数组末尾（注意：是有效数据的末尾，而不是数组物理区域的末尾）；
2、与父节点比较，如果不满足堆的性质，则交换父子节点；
3、重复步骤 2，直到满足堆的性质。

提示： 从数组末尾开始上浮，数组交换和一定的次数最少。

引用自 time.geekbang.org/column/arti… —— 王争著

结合代码可能更容易理解：

根节点存储在第 [0] 位
public class Heap {
    private Integer[] data;
    private int count;
    添加元素
    private void insert(Integer x) {
        int i = count;
        data[count++] = x;
        siftup(i);
    }
    上浮操作
    private void siftup(int k) {
        while (k > 0 && data[(k - 1) / 2] < data[k]) {
            swap(data, (k - 1) / 2, k);
            k /= 2;
        }
    }
}
复制代码

这段代码存在着一些不必要的赋值操作，可以优化，优化后目标元素只会赋值一次到最终位置：

参考 JDK 1.5 java.util.PriorityQueue.java

添加元素
private void insert(Integerx) {
    int i = count;
    data[count++] = x;
    siftup(i, x);
}
上浮操作
private void siftup(int k, Integer x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Integer parentE = data[parent];
        if (parentE >= x)
            break;
        data[k] = parentE;
        k = parent;
    }
    data[k] = x;
}
复制代码

2.2 下沉（取出元素）

往堆里取出元素时，需要执行下沉操作，具体步骤如下：

1、取出堆顶元素，即数组第 1 个元素（索引为 0 或 1，取决于具体实现）；
2、数组最后一个元素放到数组 1 个元素的位置；
3、与子节点比较，如果不满足堆的性质，则交换父节点与子节点中最小的那个；
4、重复步骤 3，直到满足堆的性质。

提示： 从数组头部开始下沉，数组交换和一定的次数最少，同时能够避免出现 数组空洞。

引用自 time.geekbang.org/column/arti… —— 王争著

另外，需要注意到叶子节点是没有子节点的，不需要执行下沉操作，可以提前结束。（根节点存储在第 [0] 位时，叶子节点下标为count2到count−1\frac{count} {2} 到 count-12count到count−1，根节点存储在第 [1] 位时，叶子节点下标为 count2+1到count\frac{count}{2} + 1 到 count2count+1到count）。

结合代码可能更容易理解：

根节点存储在第 [0] 位
public class Heap {
    private Integer[] data;
    private int count;
    取出堆顶元素
    int poll() {
        int k = --count;
        int result = data[0];
        int x = data[k];
        data[k] = null;
        if (k != 0) {
            siftdownV2(0);
        }
        return result;
    }
    下沉操作
    void siftdown(int k) {
        int half = count / 2;
        while (k < half) {
            int minPos = k;
            if (data[k * 2 + 1] < data[k]) minPos = k * 2 + 1;
            if (data[k * 2 + 2] < count && data[k * 2 + 2] < data[k]) minPos = k * 2 + 2;
            if (minPos == k)
                break;
            swap(data, k, minPos);
            k = minPos;
        }
    }
}
复制代码

这段代码存在着一些不必要的赋值操作，可以优化，优化后目标元素只会赋值一次到最终位置：

参考 JDK 1.5 java.util.PriorityQueue.java

取出堆顶元素
private int poll() {
    int k = --count;
    int result = data[0];
    int x = data[k];
    data[k] = null;
    if (k != 0) {
        siftdown(0, x);
    }
    return result;
}
下沉操作
private void siftdown(int k, int x) {
    注意：叶子节点没有子节点，不需要下沉
    int half = count >>> 1;
    while (k < half) {
    int child = (k << 1) + 1; // assume left child is least
    Integer childE = data[child];
    int right = child + 1;
    if (right < count && childE > data[right])
        childE = data[child = right];
        if (x < childE)
            break;
        data[k] = childE;
        k = child;
    }
    data[k] = x;
}
复制代码

2.3 建堆

前面讲的上浮和下沉操作的前提是数组本身是堆化的，那么这一节我们就来讨论建堆这一操作。

建堆可以分为 原地建堆 & 非原地建堆，原地建堆指的是将一个数组原地堆化的过程，而非原地建堆指的是输入数据一个个添加到数组中的过程。可以观察到，非原地建堆其实就是不断添加元素执行下沉操作的过程，等同于 第 2.1 节上浮操作，所以我们主要是分析原地建堆。

原地建堆可以用两种方法实现，分别为 从下往上堆化 & 从上往下堆化 ：

从下往上堆化

这种方法先将下标为 0 的第一个元素视为大小为 1 的堆，随后将下标从1到count−11到count -11到count−1的元素依次执行上浮操作。这个过程也相当于不断向这个初始大小为 1 的堆里添加元素。

从上往下堆化

这种方法先将叶子节点视为大小为 1 的堆，随后将下标从count2−1递减到0\frac{count}{2}-1递减到02count−1递减到0的节点执行下沉操作。

2.4 复杂度分析

时间复杂度

上浮 & 下沉：沿着树根节点到叶子节点的路径进行比较和交换。而一个包含 n 个节点的二叉树，树的高度为 lgnlgnlgn，所以时间复杂度为O(lgn)O(lgn)O(lgn)；
建堆：建堆的时间复杂度是O(n)O(n)O(n)，推导过程可以看参考资料，这个结论还是比较重要的。

空间复杂度堆化的过程中只是用了常量级变量，因此空间复杂度为O(1)O(1)O(1)。

3. 堆的应用 —— 堆排序

堆排序（Heap Sort） 指的是借助二叉堆实现的原地排序算法，它是一种时间复杂度为 O(nlgn)O(nlgn)O(nlgn)的不稳定的排序算法，快速排序有几分相似之处，后文我也会分析它们之间的区别。

总的来说，堆排序的过程可以分为 建堆 & 排序 两个步骤：

3.1 建堆

建堆的过程在 第 2.3 节讨论过了，假设我们要进行递增排序的话，我们就需要建立一个大顶堆（每个节点都大于等于子节点）。

特别提示： 完成建堆后，数据处于 堆有序 状态，但不是有序状态，堆有序其实只是指数据满足堆的性质（每个节点都大于等于或小于等于子节点）。

3.2 排序

建立大顶堆后，现在我们来进行排序操作，具体操作如下：

1、堆顶元素，交换到数组末尾位置，此时，最大的元素已经完成排序；
2、执行下沉操作，将数组前 n - 1 个数据重新堆化；
3、重复步骤 1 和步骤 2，直到堆的大小为 1。

整个过程相当于执行 n 次取出堆顶元素的操作，直到最后堆的大小为 1 时，数组完成排序。

引用自 time.geekbang.org/column/arti… —— 王争著

3.3 复杂度分析

时间复杂度

下沉操作的时间复杂度是O(lgn)O(lgn)O(lgn)，总共执行 n 次，因此总体的时间复杂度为O(nlgn)O(nlgn)O(nlgn)；

空间复杂度

堆排序是原地排序，建堆和排序的过程中只是用了常量级变量，因此总体的空间复杂度为O(1)O(1)O(1)。

3.4 堆排序与快速排序对比

前面提到了堆排序和快速排序的相似之处，那么两者有何不同的？

数据访问方式不同

快速排序是从数组下标依次递增访问数据，而堆排序是跳着访问的，后者更不利于命中 CPU 缓存行。

数据交换次数不同

堆排序进行堆化时，可能会改变数据原本的相对顺序，将原本相对有序的数组变得更加无序。这反而增加了逆序度，增加了执行交换操作的次数。

考虑到这两个因素，我们不难理解为什么 JDK 的 java.util.Arrays.sort()会选择使用快速排序，而不是堆排序了。

当然了，堆排序也不是完全没有价值，有一种场景堆排序就 “秒杀” 快速排序。那就是只需要取得前 k 个有序的数据时，即 Top k 问题，使用堆排序（或者称为大小为 k 优先队列），时间复杂度仅为O(nlgk)O(nlgk)O(nlgk)。

4. 堆的应用 —— 优先队列

与优先对列相似的有一种数据结构：队列，虽然它们的名称很相似，但是本质上区别是很大的：

数据结构	描述
队列	先进先出（FIFO），出队顺序由时间顺序决定
优先队列	出队顺序与入队顺序无关，而由优先级顺序决定

4.1 优先队列的实现

狭义上，优先队列指的是基于二叉堆实现的数据结构。而广义上，凡是能够实现按优先级顺序出队的数据结构都可以称为优先队列（例如 Android 领域熟知的 MessageQueue）。

提示： 当你看到优先队列这个词的时候，如果没有特殊上下文语境，指的就是基于堆实现的优先队列。

一般来说，优先队列有以下三种实现：

底层实现	入队	出队	举例
普通数组	O(1)O(1)O(1)	O(n)O(n)O(n)（扫描整个数组选择最高优先级）	/
顺序数组	O(n)O(n)O(n)（入队时维护顺序，下标靠前优先级越高）	O(1)O(1)O(1)（取出数组下标为 0 的元素）	Android MessageQueue
堆	O(lgn)O(lgn)O(lgn)	O(lgn)O(lgn)O(lgn)	Java PriorityQueue

可以观察到，基于堆的优先队列平衡了入队与出队的时间复杂度。

4.2 优先队列的优点

使用优先队列可以实现 高性能的定时器。

假设我们有一个定时器 / 消息器，里面存储是等待执行的定时任务，最笨的方法是每隔一小段时间扫描整个任务列表，筛选出到达执行时间的任务。这样做有两大弊端：

1、无效轮询：任务的执行时间可能还差很久，前面的扫描都是无效的；
2、扫描耗时：如果任务列表非常庞大，一趟扫描会非常耗时。

而如果使用优先队列，则可以规避这两个弊端，即不需要轮询，也不需要扫描整个任务列表。

需要做的是维护定时任务列表的执行优先顺序，每次从优先队列中取出队首的任务。然后计算该任务执行时间与当前时间的差值，把这个差值作为等待时间，等待这个时间之后再回来执行任务（如果等待过程中对任务列表进行操作，则需要提前唤醒）。

Android 领域的小伙伴应该对 MessageQueue 优先队列有深刻理解。虽然它并不是一个基于堆的优先队列，但是思路是一致的：如果当前时间还未到达队首消息的执行时间，那么当前线程等待，而不是轮询判断。Android 领域的小伙伴可以看看之前我写的这篇文章：《Android | 面试必问的 Handler，你确定不看看？》

5. 堆的应用 —— Top K 问题

5.1 题目描述

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

Top K 问题是一个超高频的面试算法问题，难度属于中等，它的解法有很多个，最笨的方法是先将整个数组执行快速排序，再返回排序后前 k 个数，时间复杂度为O(nlgn)O(nlgn)O(nlgn)。在这里我们主要讲使用二叉堆的解法。

5.2 解法步骤

步骤分解如下：

1、将数组前 k 个数添加到堆，建立一个大小为 k 的大顶堆；
2、依次遍历数组后续的数，如果该数比堆顶的数更小，则将堆顶元素弹出，而该数添加到堆中；
3、重复步骤 2，直到所有数据处理完毕，最终堆中元素就是最小的 k 个数。

可以发现基于二叉堆的思路是 使用大顶堆维护数据的最小的 k 个数，每次将一个数与堆顶元素比较。如果该数小于堆顶元素，说明堆顶元素不是最小 k 小个数，应当从堆里弹出，而该数添加到堆里。

5.3 复杂度分析

时间复杂度

建堆的时间复杂度是O(k)O(k)O(k)，而取堆顶元素和插入元素的时间复杂度为O(lgk)O(lgk)O(lgk)，因此总的时间复杂度为O(nlnk)O(nlnk)O(nlnk)，优于快速排序O(nlgn)O(nlgn)O(nlgn)；

空间复杂度

维护了一个大小为 k 的二叉堆，空间复杂度为O(k)O(k)O(k)。

6. 最大索引堆

Editting...

数据结构 | 微博 Top 10 热搜是怎么计算出来的？(二叉堆)

前言

系列文章

延伸文章

目录

1. 基本概念

2. 堆的基本操作

2.1 上浮（添加元素）

2.2 下沉（取出元素）

2.3 建堆

2.4 复杂度分析

3. 堆的应用 —— 堆排序

3.1 建堆

3.2 排序

3.3 复杂度分析

3.4 堆排序与快速排序对比

4. 堆的应用 —— 优先队列

4.1 优先队列的实现

4.2 优先队列的优点

5. 堆的应用 —— Top K 问题

5.1 题目描述

5.2 解法步骤

5.3 复杂度分析

6. 最大索引堆

热门文章

最新文章

相关课程

相关电子书