大根堆
根节点是最大值,下面的左右节点不需要比较大小。
小根堆
根节点是最小值,下面的左右节点不需要比较大小。
上滤、下滤调整堆序型
实际应用中,可能出现不满足堆序型的情况。
添加时上滤
实际存堆的还是数组结构,逻辑结构是堆,实际结构是数组
时间复杂度高(堆元素数量很大)
Netty HashWheelTimer
Netty自己设计的一个定时任务(延迟队列)解决方案海量的定时任务 效率比 Timer 高
时间轮算法(TimeingWheel)
Netty HashWheelTimer
Dubbo
Akka
Kafka
Quartz
没有排序过程:想像一下又一个圆,圆上均分 20 块,每块使用 双向链表 存储定时任务列表,到哪一块按顺序执行便可。
超时的解决方法
- 加入圈数 圈数太多,效率低
- 分层时间轮(Kafka)
时间轮算法在 Netty 中的体现