基于最小堆实现的时间轮事件触发器

2019-08-11

一. 什么是堆?

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点

二. 堆的分类

• 最大堆：根结点的值最大的堆，也叫大根（顶）堆。

• 最小堆：根结点的值最小的堆，也叫小根（顶）堆。

三. 堆的特点

1. 父结点与子结点之间的索引关系

假设有一个基于数组实现的从i开始索引的堆，对于索引为p的结点，左孩子索引记为left，右孩子索引记为right，它们之间有如下关系：

left  = 2*p + 1 - i;
right = 2*p + 2 - i;
p = (left - 1 + i) / 2;
p = (right - 1 + i) / 2;

四. 堆操作

注：以下操作基于数组实现

1. init：堆初始化

2. insert：向堆中插入一个新结点

   向数组尾部添加一个结点，并将此结点进行上浮操作，使其符合堆的性质

3. deleteTop：删除堆顶结点

   先将堆顶结点与尾结点交换，再将新的堆点结点进行下沉操作，使其符合堆的性质

4. up：将结点上浮使其符合堆的性质

   将待上浮结点与其父结点，根据最小堆还是最大堆特性进行比较，如果不需要进行上浮则退出，如果满足上浮条件，则进行上浮，并继续上浮新的父结点，直到堆顶

5. down：将结点下沉使其符合堆的性质

   将待下沉结点与其左右子结点，根据最小堆还是最大堆特性进行比较，如果不需要进行下沉则退出，如果满足下沉条件，则进行下沉，并继续下沉新的子结点，直到堆尾

6. getTop：获取当前堆顶结点的值

7. getLeftIndex：获取左孩子索引

8. getRightIndex：获取右孩子索引

9. getParentIndex：获取父结点索引

10. getTopIndex：获取堆顶结点索引

11. getLastIndex：获取堆尾结点索引

12. empty：堆是否为空

13. size：返回堆结点数量

五. 编译说明

g++ -std=c++11 -o timerheap main.cpp -lpthread