1 优先级队列

优先级队列,我的理解就是一个有排序顺序的队列,对于一般的队列,都是 FIFO,但是对于优先级队列,队列内部的顺序并不是 FIFO 的,在入队的时候需要进行一次排序,确定其在队列中的问题,然后根据顺序出队。

堆完全可以用来实现优先级队列,甚至可以说,堆本身就是一个优先级队列

2 利用堆求 Top K

对于静态数据集,我们只需要维护一个容量大小为 K 的小顶堆,在开始的时候遍历一遍数据,如果遍历到的数据比小顶堆堆顶的数据大,那么就删掉小顶堆的堆顶数据,将该数据插入到堆中,然后完成一次堆化,这样遍历数组需要的时间是 O(n),每次堆化的时间是O(logK),所以需要的时间复杂度是 O(nlogn)。

对于动态数据集,我们只一直维持这个小顶堆,在新进来数据的时候,将数据和小顶堆的堆顶数据做比较即可。这样子哪怕数据上亿也不怕