search

lewenweijia / notes

🏊 dive dive diving
1 stars 0 forks source link

堆的应用 #27

Open lewenweijia opened 4 years ago

lewenweijia commented 4 years ago 
堆的经典应用问题类型:
  1. 优先队列
  2. top k问题
  3. 中位数

例子问题?:
1. 假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何[快速]获取热门榜
   Top 10 的搜索关键词呢

极客时间版权所有: https://time.geekbang.org/column/article/70187
lewenweijia commented 4 years ago

优先队列

普通队列和优先队列?:
1. 普通队列先进先出
2. 优先队列按照优先级, 随意进优先出. 谁的优先级高谁先出, 就算是最尾巴进来, 也有可能下一次
    出去的是它的哦, 哈哈

优先队列的经典具体问题?:
1. 合并多个有序小文件(关键优化点?: 减少每次的遍历比较)
2. 高性能定时器 (小顶堆, 最快要执行的定时器在根上)
3. Top K问题(维护一个大小为K的大顶堆 -> )

经典问题 -> 夫曼编码、图的最短路径、最小生成树算法

通过哈希算法进行分片到多个文件中的啊
 -> 可怕, 各种形式的符合操作的呢