数据结构 - 堆

概述

堆是一种特殊的树,它有以下两个特点:

  • 堆是一颗完全二叉树;
  • 堆中某个节点的值不大于或不小于父节点的值;

其中,根节点的值是最大的堆叫做大顶堆,根节点的值是最小的堆叫做小顶堆。具体如下图:

前面也说了,堆是一颗完全二叉树。下图就是一颗完全二叉树,也是一个小顶堆:

完全二叉树的节点都是比较紧凑的,并且具有一定的层次关系,所以可以使用数组来存储,这样比较节省空间。上图中的完全二叉树存放到数组中如下:

这里为了方便描述,下标为 0 的位置不存储元素,从下标为 1 的位置开始存储元素。每层依次从左到右放到数组中,这样就可以保证父子节点的关系了

  • 已知节点 8,那么 8 的父节点就是:5/2=2,也就是 5 这个节点的位置
  • 已知节点 5,那么 5 的左右子节点分别是:2*2=4,也就是节点 7;2*2+1=5,也就是节点 8;

插入元素

堆中插入新的元素后,需要继续满足堆的两个特性:

  1. 堆是一颗完全二叉树;
  2. 堆中某个节点的值要么不大于(或不小于)其父节点的值;

为了满足特性 1,我们把新元素插入到最后一层的最后一个节点的后面,但是插入之后可能不再满足特性 2 ,这个时候就需要调整堆了。下面我们举例说明。

我们需要向前面的小顶堆中插入元素 2 ,我们把它放在 9 后面,这时虽然满足特性 1 ,但是不满足特性 2,这个时候就要调整堆。具体过程如下:

上述调整过程的原则是,自下而上进行调整。

从二叉树角度看:插入的节点与它的父节点相比,如果比父节点小,就交换它们的位置,重复这个过程,一直往上和父节点相比,直到比父节点大或者到根节点为止。
从数组角度看:插入的节点与 n/2 位置的节点相比,如果比 n/2 位置的节点小,就交换它们的位置,再往前与 n/4 位置的节点相比,如果比 n/4 位置的节点小,就交换位置,以此类推,直到比 n/(2^x)位置的节点大或者到顶级父节点为止。

从插入元素的过程,我们可以知道插入元素的时间复杂度为 O(logn) 。

弹出堆顶元素

从堆中弹出元素,同样需要继续满足堆的两个特性:

  1. 堆是一颗完全二叉树;
  2. 堆中某个节点的值要么不大于(或不小于)其父节点的值;

从堆顶弹出元素后,为了满足特性 1,我们把最有一个元素移到根节点(顶节点)的位置,但是不满足特性 2,这个时候需要调整堆。具体如下:

上述调整过程的原则是,自上而下进行调整。

从二叉树角度看:把最后一个节点放到堆顶,然后与左右子节点中较小的交换位置,重复这个过程,依次往下,直到其比左右子节点都小的或到达最后一层为止。
从数组角度:把最后一个元素移到下标为 1 的位置,然后与下标为 2 和 3 的元素对比,发现 8 比 2 大,且 2 是下标为 2 和 3 中较小的,然后与 2 交换位置。依次类推,再和下标为 4 和 5 的元素对比,直到没有比其更小的元素或没有左右子节点为止。

从弹出堆顶元素的过程,我们可以知道对应的时间复杂度为 O(logn) 。

建堆

建堆的过程其实就是依次插入元素的过程,一个元素的比较次数与它的高度成正比,建堆的时间复杂度为 O(n)。

堆排序

对于一个待排序的数组序列,可以将堆顶元素与第 n 个元素交换位置,再把前 n-1 个元素进行调整;再把堆顶元素与第 n-1 个元素交换位置,再把前 n-2 个元素进行调整;…..,以此类推。最后,数组中的元素就整个变成有序的了,排序也就完成了。

堆排序的时间复杂度为 O(nlogn)。

小结

堆是一种重要的数据结构,利用堆排序的场景有很多,比如 MySQL order by 语句可能会使用到堆排序;优先级队列会使用堆排序调整元素优先级;等等。