定时器为什么常用小顶堆实现？它和时间轮有什么区别？

简化版

定时器常用小顶堆，是因为堆顶永远是最近要触发的任务。

每次新增定时任务按触发时间入堆，调度线程只需要查看堆顶是否到期。到期就弹出执行，没到期就等待一段时间。

小顶堆适合任务数量中等、时间精度要求明确的场景；时间轮更适合海量定时任务和相对粗粒度的超时管理。

详细版

定时任务可以抽象成：

task = (expireAt, callback)

小顶堆按 expireAt 排序，最早到期的任务在堆顶。

操作	小顶堆复杂度
新增任务	`O(log n)`
查看最近任务	`O(1)`
弹出到期任务	`O(log n)`

如果堆顶任务还没到期，说明其他任务更不可能到期，因为它们的触发时间都不早于堆顶。

时间轮则把时间切成槽位，任务挂到未来某个槽里，插入接近 O(1)，但精度和跨度设计更复杂。

完整版教学

1. 定时器问题到底在维护什么

定时器要解决的是「谁最先到期」。

每个任务可以看成一个二元组：

(expireAt, task)

调度器不断检查当前时间 now，如果 expireAt <= now，任务就应该被触发。

这和优先队列天然匹配：优先级就是到期时间，到期时间越早优先级越高。

2. 为什么用小顶堆

小顶堆保证最小元素在堆顶。

如果用到期时间作为 key，那么堆顶就是最近要触发的任务。

while heap not empty:
  task = heap.peek()
  if task.expireAt <= now:
    heap.poll()
    run(task)
  else:
    wait(task.expireAt - now)

定时器堆的关键不是排序全部任务，而是始终知道最近一个任务。

3. 为什么只看堆顶就够了

小顶堆的堆顶是最早到期任务。

如果堆顶都没到期，那么其他任务的到期时间只会更晚，因此也不会到期。

这让调度线程可以避免扫描全部任务。

做法	检查到期任务成本
普通列表	可能每次 `O(n)` 扫描
小顶堆	只看堆顶，弹出时 `O(log n)`

这就是定时器堆比普通数组列表更合适的原因。

4. 新增和取消任务怎么处理

新增任务很简单：入堆后上浮。

取消任务更麻烦，因为普通堆不擅长删除任意元素。工程里有两种常见方案：

任务对象带 cancelled 标记，堆顶弹出时发现取消就跳过。
维护任务 id 到堆下标的映射，做索引堆，取消时直接定位删除。

if task.cancelled:
  discard
else:
  execute

第一种实现简单，第二种内存更可控。

5. 周期任务怎么处理

周期任务执行完后，可以重新计算下一次 expireAt，再放回小顶堆。

需要注意两种语义：

语义	下一次时间
固定速率	基于计划时间加 interval
固定延迟	基于实际完成时间加 delay

如果面试官问定时任务堆，补充这点会显得很工程。

6. 时间轮解决了什么

时间轮把时间切成一格一格的槽。

例如每格 100ms，有 60 个槽，就表示一圈 6s。任务根据到期时间挂到对应槽里，指针每过一格处理一个槽。

它的优势是插入和触发批处理成本低，适合海量连接超时、心跳检测、缓存过期等场景。

7. 小顶堆和时间轮怎么选

可以这样对比：

维度	小顶堆定时器	时间轮
插入	`O(log n)`	接近 `O(1)`
精度	比较灵活	受槽粒度影响
实现复杂度	较低	较高
海量任务	压力较大	更适合
最近任务查询	很直接	依赖指针推进

如果任务量不是特别夸张，小顶堆简单可靠；如果是百万级连接超时，时间轮更常被考虑。

8. 常见误区与追问

误区：定时器必须把所有任务完整排序。 不需要，只要快速找到最近到期任务即可。
误区：小顶堆取消任务一定很高效。 普通堆删除任意元素不高效，通常要懒取消或索引堆。
误区：时间轮一定比小顶堆好。 时间轮适合海量和粗粒度超时，但精度、跨度和实现复杂度要权衡。
追问：堆顶没到期时为什么可以等待？ 因为堆顶已经是最早到期任务，其他任务更晚。
追问：周期任务如何避免漂移？ 要区分固定速率和固定延迟，前者按计划时间推进，后者按完成时间推进。

简化版

详细版