跳至主要內容

 

labuladong原创约 1821 字大约 6 分钟

二叉堆(Binary Heap)没什么神秘,性质比二叉搜索树(Binary Search Tree)还简单。

二叉堆的主要操作就两个,sink(下沉)和 swim(上浮),用以维护二叉堆的性质。

二叉堆的主要应用有两个,首先是一种很有用的数据结构优先级队列(Priority Queue),第二是一种排序方法堆排序(Heap Sort)。

这个可视化面板直观地展示了二叉堆的基本操作,你可以点击跳转执行其中的代码,或自己修改代码玩一玩:

下面我就结合可视化面板来展示二叉堆的原理,最后以优先级队列为例,展示二叉堆的代码实现。

什么是二叉堆

一句话总结

一句话总结,二叉堆就是一种能够动态排序的数据结构。

所谓动态排序,就是说我们可以不断往数据结构里面添加或删除元素,数据结构会自动调整元素的位置,使得我们可以有序地从数据结构中读取元素。这是类似 快速排序归并排序 等排序算法做不到的。

能动态排序的常用数据结构其实只有两个,一个是优先级队列(底层用二叉堆实现),另一个是二叉搜索树。二叉搜索树的用途更广泛,优先级队列能做的事情,二叉搜索树其实都能做。但优先级队列的 API 和代码实现相较于二叉搜索树更简单,所以一般能用优先级队列解决的问题,我们没必要用二叉搜索树。

二叉堆是怎么做到动态排序的呢?这就要说到二叉堆这种结构的性质了。

二叉堆的性质

你可以认为二叉堆是一种特殊的二叉树,这棵二叉树上的任意节点的值,都必须大于等于(或小于等于)其左右子树所有节点的值。如果是大于等于,我们称之为「大顶堆」,如果是小于等于,我们称之为「小顶堆」。

对于小顶堆,每个节点下方的所有节点的值都比它小,那么不难想象根节点就是整棵树上的最小值。同理,大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。

我的可视化面板支持最大堆和最小堆的展示,我分别创建了一个大顶堆,一个小顶堆,你可以观察一下二叉堆的性质,注意当我们插入或删除元素时,二叉堆会自动调整以保持这种性质:

可以看到,我用 push 方法向小顶堆乱序插入若干元素,然后调用 pop 方法不断从堆顶弹出元素,小顶堆会自动调整其结构符合小顶堆的性质,最终得到的就是一个有序序列。

那么二叉堆是如何自动调整其结构,以维护堆的性质的呢?这个后面讲代码实现的时候会说。

最常见的应用:优先级队列

其实上面的可视化面板展示的就是优先级队列,它主要有三个 API:

class MyPriorityQueue {
    // 在二叉堆堆顶插入一个元素,时间复杂度 O(logN)
    // N 为当前二叉堆中的元素个数
    void push(int x);

    // 返回堆顶元素,时间复杂度 O(1)
    // 该堆顶元素就是二叉堆中的最大值或最小值,取决于是最大堆还是最小堆
    int peek();

    // 删除堆顶元素,时间复杂度 O(logN)
    int pop();

    // 返回堆中元素的个数,时间复杂度 O(1)
    int size();
}

不同编程语言提供的 API 名字可能不同,但其效果和底层实现是大同小异的。

当然,自动排序是有代价的,注意优先级队列 API 的时间复杂度,增删元素的复杂度是 O(logN),其中 N 是当前二叉堆中的元素个数,回头在算法题里面用到这种结构的话,你得会计算总的时间复杂度。

为啥叫优先级「队列」?

有的读者可能会问,这明明就是二叉堆,为啥非要叫他优先级队列呢?

主要是因为这个数据结构的 API 和我们之前讲的 标准队列 API 很像,标准队列是先进先出的顺序,而二叉堆可以理解为一种会自动排序的队列,所以叫做优先级队列感觉也挺贴切的。

当然,你也一定要明白,虽然它的 API 像队列,但它的底层原理和二叉树有关,和队列没啥关系。

另一种应用:堆排序

这种排序算法其实不用专门去学的。它的原理特别简单,就相当于把一个乱序的数组都 push 到一个二叉堆(优先级队列)里面,然后再一个个 pop 出来,就得到了一个有序的数组:

// 堆排序伪码,对 arr 原地排序
// 时间复杂度 O(NlogN),空间复杂度 O(N)
int[] heapSort(int[] arr) {
    int[] res = new int[arr.length];
    MyPriorityQueue pq = new MyPriorityQueue();
    for (int x : arr)
        pq.push(x);
    // 元素出堆的顺序是有序的
    for (int i = 0; i < arr.length; i++)
        res[i] = pq.pop();
    return res;
}

当然,正常的堆排序算法的代码并不依赖优先级队列,且空间复杂度是 O(1)。那是因为它把 pushpop 的代码逻辑展开了,再加上直接在数组上原地建堆,这样就不需要额外的空间了。

但堆排序的本质还是依靠二叉堆的性质来排序元素,等我手把手带你实现优先级队列之后,你就可以自己实现堆排序了。

在数组上原地建堆?

这里提到了在数组上原地建堆,细心的读者可能会有疑惑:刚才不是说二叉堆是一种特殊的二叉树吗?可视化面板中显示的二叉堆也是二叉树的形态,怎么可能不使用额外的空间复杂度,直接在数组上原地创建二叉树呢?

这个问题很好,我在 学习数据结构和算法的框架思维 中有阐述其中的原因。

二叉树是一种逻辑概念,并不是说只有 TreeNode 类构造出来的那个结构才是二叉树,其实数组也可以抽象成一棵树,一切递归分治的思想都可以抽象成一棵树,递归函数的那个递归栈也可以理解成一棵树,

当然,如果你是初学者,上面这句话你可能看起来有些绕。不用着急,后面的文章会让你的理解更加深入,等你真的理解这句话之后,所有的算法对你来说都小菜一碟了。

上次编辑于: