动画：什么是堆？

写在前边

通常我们在某些新闻类、资讯类、以及微博等网站的首页看到一些实时推送的热点信息。

比如像微博这种实时更新的热搜事件是如何在海量的数据中根据用户的热度以及搜索最多的关键字，快速的筛选出来进行排序，每过几分钟就更新一次，然后将最热门的信息展现给用户，如果用今天文章中分享到的堆是如何实现呢？

思维导图

什么是堆？

在之前文章中分享过二叉树这个数据结构，其实对堆这种数据结构就是对二叉树的一个变体。

那什么是堆呢？堆是一个完全二叉树，堆中的每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。如下图所示：

通过上边的定义我们可以分为大顶堆和小顶堆。每个节点的值大于等于子树每个节点值的堆叫做「大顶堆」；每个节点的值小于等于子树中每个节点值的堆叫做「小顶堆」。

如何实现一个堆？

我们知道了堆的定义以及特点和分类，我们用什么来存储堆这种数据结构，我们还是老样子，通过已经学过的数据结构来进行延伸。

对于二叉树来说，两种存储方式，一种是链表，另一种就是数组的方式。那么堆作为二叉树的变体，堆的存储还是通过数组来存储的。

数组中下标为 i 的节点的左子节点就是下标为 i2 的节点，右子节点就是下标为 i 2+1 的节点，父节点就是下标为 i/2 的节点。

如果我们想在堆中插入一个数据，我们称之为「堆化」。有两种插入方式，分别是从上往下堆化和从下往上堆化。

1、从下往上堆化

当我们插入一个数据的时候，将这个数据插入到最后的结点(也就是数组的最后位置)，然后开始和父节点进行比较大小，如果当前为大顶堆的时候，该结点大于父节点，则进行交换。然后继续和父节点进行比较，直到满足大顶堆的条件位置。

2、从上往下堆化

当我们删除一个堆顶的元素时候（因为堆顶不是最大值就是最小值），这时候我们将堆顶的元素删除需要将第二大元素放到堆顶，如果我们还是按照以上方法进行从上往下堆化的时候，会出现数组中某个元素为空的情况。

(这样会让数组中某个元素为空)

所以我们在堆中删除一个元素，先把堆顶的元素删除之后，将最后一个节点放到堆顶，然后按照上边的方法进行交换，直到父子节点满足堆的条件关系，我们称之为从上往下堆化。

堆的性能效率

对于堆这种数据结构来说，通过堆的插入和删除元素，堆也可以用排序，也就是堆排序，对于堆排序会在以后的文章单独写一篇。

那么堆的性能效率如何，分析到性能效率，我们从时间复杂度和空间复杂度去分析。对于一个拥有 n个节点的完全二叉树，树的高度不会超过 log2n，堆化的过程就是顺着路径进行交换的过程，时间复杂度与树的高度成正比，也就是 O(logn)。

堆的应用

1、应用一：优先级队列

堆最常用的应用是在优先级队列中，顾名思义，队列是先进先出，而这里的优先级队列的出队顺序不是先进先出，而是按照优先级来的，优先级越高就先出队。

用堆实现实现一个优先级队列的话，就可以把堆看做一个优先级队列，往优先级队列中插入一个元素，就相当于往堆中插入元素，删除一个元素，就相当于取出一个堆顶元素。

这要保证对顶元素大于等于其他元素，所以一般采用大顶堆。

最常见的一个优先级队列问题就是定时器问题。我们有个定时器，定时了一些任务，每个任务都会进行倒计时，倒计时到零之后，就会去执行。

用传统的方法的话，每隔一秒都要扫描遍历一些所有的任务，看哪个任务的计时器倒计时结束了就去执行，这样在性能上比较低。

如果我们使用小顶堆来处理这个问题，那么效率就提高了，对所有任务进行一个堆化，堆顶元素就是最先执行的任务，每执行完一个任务就要重新计算倒计时的时间，得出最先要执行的那个任务。

2、求前 n 大数据

也就是我们开题提出的问题，在大量的数据中如何求出前 n 大数据。

首先我们想到用什么求序列化数据？每个都是一个事件，没法进行统计，但是每个事件都会有对应的关键词，用户每点击或者阅读一篇事件的文章就会提高该对应关键词的权重。

我们最先要做的统计出有哪些关键词，关键词搜索的次数也要进行统计。有了这些数据之后，一个最主要的问题来了，随着用户的搜索，关键词的次数是动态数据，而不是我们所谓的静态数据。

如果是静态数据的话，这个好办，首先维护一个大小为 n 的小顶堆，顺序遍历如果取出的数据比堆顶大，我们呢就将堆顶元素删除，然后将数据进行插入。如果比堆顶的元素小，我们就不做处理。将数组全部遍历完成之后，堆中的数据就是前 n 大数据。数组，从数组中取出数据与堆顶元素比较。

那么对于动态数据我们应该如何去做呢？也就是实时求取前 n 大数据。

我们一直维护一个 n 大小的小顶堆，当有数据被添加进来的时候，就拿着它与堆顶的元素对比。如果比堆顶元素大，我们就删除堆顶元素，将此元素进行插入，如果比堆顶小，我们就不做任何处理。

小结

今天我们主要分享了堆这种数据结构，以上是堆一些最基本的概念和应用，通过以上我们可以延伸出很多的问题，实际中，微博的数据量是很庞大的，亿万级的数据，如果快速的统计出关键字，如果只是单机操作，是非常受局限性的。

我们会采用多机操作，也就是多台机器进行同时统计，这部分会涉及数据的分片，从而加快效率，除此之外，我们还会用到一些其他高效率的数据结构。

比如之前所分享到的散列表以及以后分享到的平衡二叉树这些支持快速增删改查的数据结构来进行统计。

话说回来，微博这么多的用户，内部肯定有很多的优化和设计，而不是简单的几个数据结构就能够解决的。

问题思考

最后留两个问题思考，可以在留言区写下你的思考，从而检验你对堆是否真正的掌握熟练了。

1、对于上述微博静态数据和动态数据的性能效率多高，也就是时间和空间复杂度能不能自己分析出来？

2、作为一个前端工程师，让你在一家广告公司网站上，在首页每隔 10 分钟显示点击量前 10 的广告，你如何进行设计和处理呢？