二叉堆(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)
。那是因为它把 push
和 pop
的代码逻辑展开了,再加上直接在数组上原地建堆,这样就不需要额外的空间了。
但堆排序的本质还是依靠二叉堆的性质来排序元素,等我手把手带你实现优先级队列之后,你就可以自己实现堆排序了。
在数组上原地建堆?
这里提到了在数组上原地建堆,细心的读者可能会有疑惑:刚才不是说二叉堆是一种特殊的二叉树吗?可视化面板中显示的二叉堆也是二叉树的形态,怎么可能不使用额外的空间复杂度,直接在数组上原地创建二叉树呢?
这个问题很好,我在 学习数据结构和算法的框架思维 中有阐述其中的原因。
二叉树是一种逻辑概念,并不是说只有 TreeNode
类构造出来的那个结构才是二叉树,其实数组也可以抽象成一棵树,一切分治穷举的思想都可以抽象成一棵树,递归函数的那个递归栈也可以理解成一棵树。
当然,如果你是初学者,上面的话你可能看起来有些绕。不用着急,后面的文章会让你的理解更加深入,等你真的理解这句话之后,所有的算法对你来说都小菜一碟了。