堆的应用

堆的应用一：优先级队列

将优先级的之分的数据存入堆中（小顶堆或者大顶堆），堆顶即优先级最搞的数据，当需要的时候直接取堆顶，然后堆顶补充下一优先级数据，由于堆堆顶插入或者删除数据时间复杂度都是O(logn)，所以效率很高。

• 合并有序小文件
  加入由100个小文件，每个文件中存放的都是一些有序的字符串片段，如果要合并成一个大文件，用常规的数组取字符串需要遍历整个数组，若将从小文件中取出来的字符串放到小顶堆中，每次取堆顶字符串然后删除，效率提高。
• 高性能定时器
  我们按照任务设定的执行时间，将这些任务存储在优选级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。

堆的应用二：利用堆求Top k

我们可以维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前K 大数据了。

堆的应用三：利用堆求中位数

我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

图1