堆应用

应用一：优先级队列

1. 优先级队列，数据的出队顺序不是先进先出，而是而是按照优先级来，优先级最高的，最先出队。
2. 实现一个优先级队列方法很多，但是用堆来实现是最直接，最高效的，这是因为堆和优先级队列非常相似。一个堆可以看作一个优先级队列，很多时候，他们只是概念上的区分。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。
3. 优先级队列的应用广泛，如赫夫曼编码，图的最短路径，做小生成树的算法等等

优先级队列应用一：合并有序小文件

假设：有100个小文件，每个文件大小为100MB，每个文件中储存的都是有序的字符串。现需要将这100个小文件合并成一个有序的大文件。
思路：

1. 整体思路有点像归并排序中的合并函数，从100个文件中，各取第一个字符串，放入数组中，然后比较大小，把最小的那个字符串合并后的大文件中，并从数组中删除。
2. 假设，最小的字符串来自于13.txt这个文件，就再次从这个文件找那个取下一个字符串，放到数组中，重新比较大小，并且选择最小的放入合并后的大文件，将它从数组中删除。依次类推，直到所有的文件中的数据都放入到大文件为止。
3. 使用数组来存储从小文件中取出来的字符串，每次从数组中取最小字符串，都需要循环遍历整个数组，效率不高。
4. 可以用到优先级队列，也可以说是堆。将从小文件中取出的字符串放入到小顶堆中，堆顶的元素就是优先级队列队首的元素，就是最小的字符串。
5. 依次从小文件中取出下一个字符串，放入到堆中，循环这过程。

删除堆顶数据和往堆中插入数据的时间复杂度都是O(logn)，n表示堆中的数据个数，这里就是100

优先队列应用二：高性能定时器

假设：有一个定时器，定时器中维护了很多定时任务

1. 每过1秒就扫描一遍任务列表做法太低效。原因1：任务的约定执行时间离当前时间可能还有很久，大量的扫描徒劳无功。原因2：每次都要扫描整个任务列表，若列表较大，会比较耗时。
2. 针对这种文件，可用优先队列来解决。按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（最小顶堆）存储的是最先执行的任务。
3. 这样定时器就不用每隔一秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，即可得到一个时间间隔T。
4. 当T秒时间过去后，定时器取优先级队列中队首的任务执行，然后在计算新的队首任务的执行时间点和当前时间点的差值。
5. 这样定时器就不用间隔1秒就轮询一次，也不用遍历整个任务列表，性能就提高了。

应用二：利用堆求Top K

求Topk的问题可抽象成两类：

1. 针对静态数据
   可以维护一个大小为k的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果堆顶元素大，就将堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前k大数据了。
   遍历数据需要O(n)的时间复杂度，一次堆化操作需要O(logk)的时间复杂度，最坏情况下，n个元素都入堆一次，时间复杂度就是O(nlogk)。

2. 针对动态数据求得Topk就是实时Topk。
   一个数据集合有两个操作，一个是添加数据，另一个询问当前的前k大数据。
   可以维护一直都维护一个k大小的小顶堆，当有数据被添加到集合时，就那它与堆顶的元素对对比。如果比堆顶元素大，就把堆顶元素删除，并将这个元素插入到堆中，如果比堆顶元素小，这不处理。这样，无论任何时候需要查询当前的前k大数据，就都可以 立刻返回给他。

应用三：利用堆求中位数

1. 对于一组静态数据，中位数是固定的，可以先排序，第n/2个数据就是中位数。
2. 对于动态数据集合，就无法先排序了，需要借助堆这种数据结构，我们不用排序，就可以非常高效的实现求中位数操作。

实现思路：

1. 需要维护两个堆，大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。
2. 即：如果有n个数据，n是偶数，从小到大排序，那前n/2个数据存储在大顶堆中，后n/2个数据存储在小顶堆中。这样，大顶堆中堆顶元素就是要找的中位数。
3. 如果新加入的数据小于等于大顶堆的堆顶元素，就将这个数据插入到大顶堆；否则就插入小顶堆
4. 当两个堆中的数据量不服和中位数的约定时，就从一个堆中不停的将堆顶的元素移动到另一个堆，重新让两个堆中数据满足上面的约定。

于是，可以利用两个堆实现动态数据集合中求中位数的操作，插入数据因为涉及堆化，所以时间复杂度变成了O(logn)，但求中位数只需要返回大顶堆的堆顶元素就可以了，所以时间复杂度就是O(1)。

思考题

有一个访问量非常大的新闻网站，我们希望将点击量排名 Top 10 的新闻摘要，滚动显示在网站首页 banner 上，并且每隔 1 小时更新一次。如果你是负责开发这个功能的工程师，你会如何来实现呢？

1. 对每篇新闻摘要计算一个hashcode，并建立摘要与hashcode的关联关系，使用map存储，以hashCode为key，新闻摘要为值；
2. 按每小时一个文件的方式记录下被点击的摘要的hashCode；
3. 当一个小时结果后，上一个小时的文件被关闭，开始计算上一个小时的点击top10；
4. 将hashcode分片到多个文件中，通过对hashCode取模运算，即可将相同的hashCode分片到相同的文件中；
5. 针对每个文件取top10的hashCode，使用Map<hashCode,int>的方式，统计出所有的摘要点击次数，然后再使用小顶堆（大小为10）计算top10；
6. 再针对所有分片计算一个总的top10,最后合并的逻辑也是使用小顶堆，计算top10；
7. 如果仅展示前一个小时的top10,计算结束；
8. 如果需要展示全天，需要与上一次的计算按hashCode进行合并，然后在这合并的数据中取top10；
9. 在展示时，将计算得到的top10的hashcode，转化为新闻摘要显示即可。