# timer_heap

**Repository Path**: debugview/timer_heap

## Basic Information

- **Project Name**: timer_heap
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-05-15
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

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

**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`