背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

使用堆分清主次

优先队列

队列是一种按先进先出（FIFO）顺序处理数据的列表。只能从队列的末尾插入数据，从队列的开头读取和删除数据。我们需要按照数据插入队列的顺序进行读取。

优先队列的删除和读取与传统队列一样，但其插入类似于有序数组。删除数据和读取数据依然只能从优先队列的开头进行，但是插入需要确保数据总是按特定顺序排列。

优先队列也是一种抽象数据结构。它可以使用其他更基础的数据结构来实现。最直接的一种实现是使用有序数组。我们需要给数组加上以下限制。

• 插入数据时，需要确保数组顺序。
• 数据只能从数组末尾移除。（数组末尾表示优先队列的开头。）

这种方法非常简单直接。下面来分析一下它的效率。

优先队列有两种主要操作：删除和插入。

使用数组的末尾来表示优先队列的开头。这样就能一直从数组末尾删除元素，即需要O(1)步。

基于数组的优先队列有着O(1)时间的删除和O(N)时间的插入。如果优先队列中有很多数据，那么O(N)时间的插入可能会拖慢应用速度。

堆

二叉堆是一种特殊的二叉树。再提醒你一下，二叉树的每个节点最多只有两个子节点。

即使是二叉堆也有两类：最大堆和最小堆。先来学习最大堆，但是你稍后就会发现二者其实没什么区别。

堆是一棵满足如下条件的二叉树。

• 每个节点的值都大于其所有后代节点的值。这个规则也被称为堆条件。
• 树必须是完全的。

堆条件

堆条件说的是每个节点的值必须大于其每个后代节点的值。

堆的结构和二叉查找树非常不同。二叉查找树每个节点都小于其右子节点，而堆的节点绝不能小于其后代节点。俗话说：“二叉查找树不成堆。”

还可以构建一个有着相反堆条件的堆，也就是每个节点都必须小于其后代节点。这样的堆就是刚才提过的最小堆。我们会继续关注最大堆，也就是每个节点都必须大于其所有后代节点的堆。说到底，一个堆到底是最大堆还是最小堆其实无关紧要。除了堆条件相反，两种堆是完全一致的。此外，它们的基本思想也是一样的。

完全树

完全树是填满了节点的树，其中不存在缺失的节点。如果从左向右检查每层节点，你就会发现每个节点都存在。不过，最下面的一行有可能有空位置，只要空位置的右边没有节点就行。

堆就是一棵满足堆条件的完全树。

堆的性质

和二叉查找树相比，堆被认为是一种弱排序的数据结构。虽然堆的确有一些顺序要求（后代不能大于祖先），但这不足以支持查找。

堆的另一个特性现在可能已经很明显了，不过还是要提一句：堆的根节点的值总是最大的。（在最小堆中，根节点的值最小。）这也是堆适合实现优先队列的关键所在。我们希望在优先队列中访问有最高优先级的值。如果用堆来实现，那么我们就能确定这个值肯定位于根节点。因此，根节点就表示有着最高优先级的数据。

堆有两种主要操作：插入和删除。正如我们注意到的，因为堆查找需要检查每个节点，所以堆通常不需要实现查找。

堆有尾节点的概念。堆的尾节点就是最下面一层的最右边的节点。

堆的插入

要把新数据插入堆，需要按下面的算法来操作。

(1) 创建一个新节点存储新值，把它插入最下面一层右边空缺的第一个位置中。这样，这个值就成了堆的尾节点。

(2) 比较新节点和其父节点。

(3) 如果新节点大于其父节点，就交换它们的位置。

(4) 重复第(3)步，从而把新节点向上移动，直到其父节点的值大于它的值。

这个把新节点沿着堆向上移动的过程称为上滤。节点有时向右移动，有时向左移动，但它总是在向上移动，直到找到正确位置。

堆的插入操作的效率是O(log N)。如果二叉树有N个节点，那么它就有大约log N行。因为最多只需要把新的值上滤到最上面一行，所以最多需要log N步。

总结

堆也是一种树，它非常适合特定场合，尤其是那些需要一直记录数据集中的最大值或最小值的情况。

二叉查找树的查找飞快，同时插入成本很低。而堆是实现优先队列的完美数据结构。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。