数据结构与算法之美 | 学习笔记25 —— 堆的应用

应用一：优先级队列

在优先级队列中，数据的出队顺序按照优先级来，优先级最高的最先出队。用堆来实现优先级队列比较高效。因为往优先级队列中插入元素，相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，相当于取出堆顶元素。优先级队列可以应用于赫夫曼编码、图的最短路径、最小生成树算法；Java的PriorityQueue, C++的priority_queue等。

1. 合并有序小文件

将100个存有有序字符串的100M小文件合并为一个大的有序文件：
思路比较像归并排序中的合并过程。先从100个文件中各取第一个字符串放入数组，比较大小后把最小的放入大文件中，并从数组中删除，再从这个最小所在文件中取下一个字符串，对数组重新比较大小，循环往复。
这种方式每次比较需要遍历，但如果用优先级队列，将上边说的数组构成小顶堆，每次取堆顶元素放入大文件中，循环往复，效率更高。
删除堆顶数据和插入数据的时间复杂度都为$O(logn)$O(logn)，n表示堆中数据个数。

2. 高性能定时器

对于维护了很多定时任务的情况，如果每一秒都扫描一遍任务，看看有没有到达执行时间，那么会很低效。如果将任务按照执行时间，存储到优先级队列中，就可以直接等待离第一个任务即将要执行的时间，再执行队首任务；之后再将新的队首任务执行时间与当前时间差值进行计算，将这个值作为定时器需要等待时间，循环往复。

应用二：利用堆求Top K

1. 静态数据

对于包含n个数据的数组，查找Top K，可以维护一个大小为K的小顶堆。顺序遍历数组，对于比堆顶元素大的数据，删除堆顶，将元素入堆，直到所有数据遍历完成。因为遍历数组需要$O(n)$O(n)，一次堆化操作要$O(logK)$O(logK)，所以最坏情况下，n个元素都入堆一次，最坏时间复杂度为$O(nlogK)$O(nlogK)。

2. 动态数据

对于动态数据求实时Top K，可以一直维护K个大小的小顶堆，每次有数据插入时都与堆顶元素对比，如果比堆顶元素大，就将堆顶元素删除，将新数据插入堆中。

应用三：求动态数据集合的中位数

对于奇数个数据，第n/2+1个数是中位数；对于偶数个数据，可以随意取最中间两个其中一个，例如第n/2个数据。

对于动态数据，对数据排序后，我们维护一个大顶堆，用来存储前半部分数据，和一个小顶堆，用来存储后半部分数据，大顶堆的数据都小于小顶堆的数据。
那么，大顶堆中的堆顶元素就是中位数。
（如果n为奇数，大顶堆有n/2+1个数据，小顶堆有n/2个数据；如果n为偶数，则都有n/2个数据）

当数据动态变化时，如果新数据小于大顶堆的堆顶元素，就插入大顶堆，否则插入小顶堆。这时两个堆的数据数量可能不平衡，这时可以将一个堆中的堆顶元素向另一个堆中移动。

插入数据涉及堆化，所以时间复杂度为$O(logn)$O(logn)，取中位数时间复杂度为$O(1)$O(1)。

延伸：求百分位的数据

例如求99%响应时间，就是从小到大排列后，这个数大于前面99%的数据。

这时，维护的两个堆大小，大顶堆就维护n99%个数据，小顶堆维护n1%个数据，大顶堆的堆顶就是99%响应时间。

实际场景：快速获取Top 10热门搜索关键词

对于包含10亿个搜索关键词的日志文件，快速获取Top 10热门搜索关键词：

1. 因为10亿数据过大，首先将文件分片：创建10个空文件，遍历10亿个关键词，通过哈希算法再同10取模的方式，将所有数据分到对应10个文件中；之后，每个文件有1亿关键词，假设每个关键词50个字节，10%的重复率，那么总大小为500M，内存可以接受；
2. 首先通过散列表（或平衡二叉查找树等支持快速查找、插入的结构）来记录关键词及出现的次数：扫描所有关键词，每扫描一个都去散列表中查询，将对应次数+1，对于不存在的关键词，将其插入散列表并次数+1；
3. 建立大小为10的小顶堆，遍历散列表，一次将关键词及搜索次数与堆顶对比，如果次数更多，就删除堆顶，插入数据到堆中；