Linux(程序设计):64---高性能定时器之时间堆 _高性能

弓背霞明剑照霜，秋风走马出咸阳。这篇文章主要讲述Linux(程序设计):64---高性能定时器之时间堆相关的知识，希望能为你提供帮助。
一、时间堆概述

前文几篇文章（javascript:void(0)、javascript:void(0)）介绍的定时方案都是以固定的频率调用心搏函数tick，并在其中依次检测到期的时间器，然后指定到期定时器上的回调函数
文本设计定时器的另一种思路：
- 1.将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。这样，一旦心搏函数tick被调用，超时时间最小的定时器必然到期，我们就可以在tick函数中处理该定时器
- 2.然后再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔
- 3.如此反复，就实现了较为精确的定时
最小堆是实现上面定时器思想的最佳选择方案

二、最小堆

最小堆的数据结构介绍，也可以参见本人的C++数据结构文章：javascript:void(0)
最小堆是指每个节点的值都小于或等于其子节点的值的完全二叉树。例如下面是一个具有6个元素的最小堆

【Linux(程序设计):64---高性能定时器之时间堆】

文章图片

最小堆的插入

最小堆的插入操作就是在最小堆最后插入一个节点，然后重新调整最小堆的结构

插入原理：
1.先将添加的新元素放在最小堆的最后一个位置

2.然后新元素与父节点进行比较（如果有父节点的话）。如果比父节点的值大，那么就结束插入操作，插入操作也到此为止；如果比父节点的值小，那么就与父节点进行位置交换

3.重复步骤2，直到无父节点或者比父节点的值大，停止插入操作

演示案例：
例如在上面的最小堆中插入元素14

文章图片

最小堆的删除

最小堆的删除操作就是删除根节点，然后重新调整最小堆的结构

删除原理：
1.将原根节点处删除

2.将最小堆的最后一个节点移动到根节点

3.然后判断子节点是否有比自己的值小，如果小，那么就与子节点进行交换（如果两个子节点都比自己的值小，那么就挑最小的进行交换）

4.重复步骤3，直至子节点的值都比自己大，结束删除操作

演示案例：
例如在上面的最小堆中删除一个元素

文章图片