计算机程序的思维逻辑 (45) - 神奇的堆

在队列中，一般是从头部删除元素，Java中用堆实现优先级队列，我们来看下如何在堆中删除头部，其基本步骤为：

1. 用最后一个元素替换头部元素，并删掉最后一个元素。
2. 将新的头部与两个孩子节点中较小的比较，如果不大于该孩子节点，则满足堆的性质，结束，否则与较小的孩子进行交换，交换后，再与较小的孩子比较和交换，一直到没有孩子，或者不大于两个孩子节点。这个过程我们般称为siftdown。

我们来看个例子。下面是初始结构：

执行第一步，用最后元素替换头部，会变为：

现在根节点16小于孩子节点，与更小的孩子节点6进行替换，结构会变为：

16还是小于孩子节点，与更小的孩子8进行交换，结构会变为：

此时，就满足堆的性质了。

从中间删除元素

那如果需要从中间删除某个节点呢？与从头部删除一样，都是先用最后一个元素替换待删元素。不过替换后，有两种情况，如果该元素大于某孩子节点，则需向下调整(siftdown)，否则，如果小于父节点，则需向上调整(siftup)。

我们来看个例子，删除值为21的节点，第一步如下图所示：

替换后，6没有子节点，小于父节点12，执行向上调整siftup过程，最后结果为：

我们再来看个例子，删除值为9的节点，第一步如下图所示：

交换后，11小于右孩子10，所以执行siftdown过程，执行结束后为：

构建初始堆

给定一个无序数组，如何使之成为一个最小堆呢？将普通无序数组变为堆的过程我们称之为heapify。

基本思路是，从最后一个非叶子节点开始，一直往前直到根，对每个节点，执行向下调整siftdown。换句话说，是自底向上，先使每个最小子树为堆，然后每对左右子树和其父节点合并，调整为更大的堆，因为每个子树已经为堆，所以调整就是对父节点执行siftdown，就这样一直合并调整直到根。这个算法的伪代码是：

void heapify() {
    for (int i=size/2; i >= 1; i--)
        siftdown(i);
}

size表示节点个数, 节点编号从1开始，size/2表示第一个非叶节点的编号。

这个构建的时间效率为O(N)，N为节点个数，具体就不证明了。

查找和遍历

在堆中进行查找没有特殊的算法，就是从数组的头找到尾，效率为O(N)。

在堆中进行遍历也是类似的，堆就是数组，堆的遍历就是数组的遍历，第一个元素是最大值或最小值，但后面的元素没有特定的顺序。

需要说明的是，如果是逐个从头部删除元素，堆可以确保输出是有序的。

算法小结

以上就是堆操作的主要算法：

• 在添加和删除元素时，有两个关键的过程以保持堆的性质，一个是向上调整(siftup)，另一个是向下调整(siftdown)，它们的效率都为O(log2(N))。由无序数组构建堆的过程heapify是一个自底向上循环的过程，效率为O(N)。
• 查找和遍历就是对数组的查找和遍历，效率为O(N)。

小结

本节介绍了堆这一数据结构的基本概念和算法。

堆是一种比较神奇的数据结构，概念上是树，存储为数组，父子有特殊顺序，根是最大值/最小值，构建/添加/删除效率都很高，可以高效解决很多问题。

但在Java中，堆到底是如何实现的呢？本文开头提到的那些问题，用堆到底如何解决呢？让我们在接下来的几节中继续探索。

---------------

未完待续，查看最新文章，敬请关注微信公众号“老马说编程”(扫描下方二维码)，从入门到高级，深入浅出，老马和你一起探索Java编程及计算机技术的本质。用心原创，保留所有版权。

（编辑：淮北站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!