数据结构基础篇-二叉堆

1,521

二叉堆分为两种,最大堆和最小堆,我们只讨论最小堆的性质,最大堆具有相同的原理。
最小堆是一种符合下面两个特性的树形结构:

  1. 最小堆是一颗完全二叉树,即最小堆的每个节点要么没有子节点,要么只有一个左子节点,要么有两个子节点。
  2. 最小堆的每个节点都小于等于它的子节点。

堆的基本操作

从性质2可以得出一个结论,最小堆的堆顶元素,一定是堆中最小的元素。
最小堆可以支持以下几种基本操作:

  1. pop,移除堆顶元素,然后堆要做一些操作,维护堆的性质,这样保证了每次都能pop出堆中最小元素
  2. peek,查看堆顶元素
  3. push,向堆中添加元素,这个元素要被移动到合适的位置,以维护堆的性质
  4. union,将两个堆合并成一个堆,需要额外的操作维护堆的性质

这其中,peek的时间复杂度是O(1)的,pop和push的操作是O(logN)的,union操作是O(N+M) 的,其中N和M是堆元素个数。这里先有个概念即可,下面会详细分析这些操作。
由堆的这些性质可以看出来,堆在处理动态数据的时候有非常大的优势,在很多优先级相关的场景下发挥着重大的作用。
堆删除和新增元素后的维护操作,我们分别称之为shiftUpshiftDown,下图展示了一个最小堆的添加和删除过程。

最小堆维护图
从上图可以直观的看出,删除堆顶元素后的shiftDown操作和添加元素后的shiftUp的时间上限和堆的高度有关系,二叉树的高度是logN的,所以我们说堆的pop和push的操作时间复杂度是O(logN)的。

堆的存储

谈到树结构,大家可能首先想到的是使用链表的方式存储,确实使用引用关联节点的方式用起来非常灵活。但是对于完全二叉树来说,使用数组存储是一种更加优雅的实现方法。同样使用数组实现二叉堆是一种非常经典的实现,下面我们就来谈谈如何使用数组实现二叉堆的。
先看一幅图

最小堆存储图
从图中淡蓝色的索引不难发现,数组中元素是按照二叉树的广度优先遍历顺序存储的,由于堆是完全二叉树,所以存储数组中元素一定是连续的。
存的问题解决了,那怎么读取呢,堆的基本操作需要频繁的获取当前节点的父节点或者子节点的。基于链表的实现方式非常简单的就能通过引用获取,那么基于数组的实现又如何获取呢?
我们还是重点关注上图中淡蓝色字体标注的树节点下标,不难发现:

  1. 每个节点的左子节点下标 = 自身下标 * 2右子节点下标 = 自身下标 * 2 + 1
  2. 每个节点父节点下标 = 自身下标 / 2,这里的除是向下取整的。

如果你对这个结果持怀疑态度,可以使用数学归纳法证明一下,也比较简单,这里就不在赘述了
可能你注意到了,数组的起始下标是从1开始的,这也是一种比较经典的实现方式(可以减少计算次数),数组的起始下标从0开始,也有相似的性质。

解决了存取问题,我们不妨看一下核心代码的实现

堆的实现

我用Java代码实现了一个二叉堆,详细的代码可以在我的GitHub上可以看到,下面是一些核心代码。

  1. 下面的代码展示了,从下标i开始做shiftUp操作
private void shiftUp(final int i) {
    for (int c = i; ; ) {
        // 取父节点下标p
        int p = c >>> 1;
        // 如果p<1表示遍历到了堆顶,
        // compare(c, p) >= 0表示当前元素大于等于父节点
        // 这两种情况都表示堆性质已经恢复,需要跳出循环
        if (p < 1 || 
            compare(c, p) >= 0) {
            break;
        }
        // 交换两个元素
        swap(c, p);
        c = p;
    }
}
  1. 下面的代码展示了,从下标i开始做shiftDown操作
private void shiftDown(final int i) {
    for (int c = i; ; ) {
        // 获取左右子节点下标
        int l = c << 1, r = l + 1;
        // 右子节点存在,就和两个子节点中较小的比较
        if (r <= size) {
            int ch = compare(l, r) < 0 ? l : r;
            if (compare(c, ch) <= 0) {
                break;
            }
            swap(c, ch);
            c = ch;
        } else if (l <= size &&
                   compare(c, l) > 0) {
            swap(c, l);
            c = l;
        } else {
            // 循环到底的情况
            break;
        } 
    }
}

堆的heapfiy

从一个数组构建堆的操作,我们姑且称之为heapify。一种很容易想到的方法是,直接遍历数组push到一个空堆中,这种做法也有着不错的时间复杂度(O(NlogN))。不过还有更优雅的做法,这种做法的时间复杂度是O(N)的。下面heapify代码非常简单,就是从数组中间向前遍历,依次做shiftDown操作,为什么要从size ÷ 2开始遍历呢?因为从这个下标开始往前的节点才有孩子节点,此时做shiftDown是有意义的。这个heapify操作的时间复杂度上界也是O(NlogN)的,不过渐渐时间复杂度是O(N)的,具体证明过程,大家可以参照《算法导论》。

private void heapify() {
    int lastParent = size >>> 1;
    for (int i = lastParent; i >= 1; i--) {
        shiftDown(i);
    }
}

堆的应用

堆是一种应用比较广泛的数据结构,在很多地方都有应用。下面我们就举两个Java中的例子。

  1. 优先级队列,普通的队列是先进先出,而优先级队列的出队总是优先级最高的元素,这很符合堆的特点。Java中提供的java.util.PriorityQueuejava.util.concurrent.PriorityBlockingQueue这两种优先级队列都是用堆实现的。
  2. Java定时任务线程池ScheduledThreadPoolExecutor中的工作队列DelayedWorkQueue其实也是一个堆的实现。

原创不易,转载请注明出处!www.yangxf.top/