时间堆原理详解及C++11实现

文档中心

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

一、背景

网络编程中除了处理IO事件之外，定时事件也同样不可或缺，如定期检测一个客户连接的活动状态、游戏中的技能冷却倒计时以及其他需要使用超时机制的功能。我们的服务器程序中往往需要处理众多的定时事件，因此有效的组织定时事件，使之能在预期时间内被触发且不影响服务器主要逻辑，对我们的服务器性能影响特别大。

一般的做法是将每个定时事件封装成定时器，并使用某种容器类数据结构将所有的定时器保存好，实现对定时事件的统一管理。常用方法有排序链表、红黑树、时间堆和时间轮，本篇文章将对时间堆方案进行详细介绍。

二、小根堆详解

传统的定时方案是以固定频率调用起搏函数tick，进而执行定时器上的回调函数。而时间堆的做法则是将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔，当超时时间到达时，处理超时事件，然后再次从剩余定时器中找出超时时间最小的一个，依次反复即可。

举个例子：

当前系统时间：8:00
1号定时器超时时间：8:05
2号定时器超时时间：8:08
…
设置心搏间隔：8:05-8:00=5
5分钟到达后处理1号定时器事件，再根据2号超时时间设定心搏间隔

以上是时间堆的基本设计思路，下面我们将时间堆的核心构件—最小堆进行介绍。

2.1 数据结构

小根堆：父节点的值小于或等于子节点的值，如下图：
在这里插入图片描述
堆的存储
一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2，它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2，如下图：

由于堆存储在下标从0开始计数的数组中，因此，在堆中给定下标为i的结点时：

（1）如果i=0，结点i是根结点，无父结点；否则结点i的父结点为结点(i-1)/2；
（2）如果2i+1>n-1，则结点i无左子女；否则结点i的左子女为结点2i+1；
（3）如果2i+2>n-1，则结点i无右子女；否则结点i的右子女为结点2i+2。

2.2 相关操作

堆的插入

插入一个元素：新元素被加入到堆的末尾，然后更新树以恢复堆的次序。
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。需要从下往上，与父节点的关键码进行比较，对调。
在这里插入图片描述
堆的删除
按定义，堆中每次都删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，堆的元素个数-1，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。
在这里插入图片描述
堆的创建
对于叶子节点，不用调整次序，根据满二叉树的性质，叶子节点比内部节点的个数多1.所以i=n/2 -1 ，不用从n开始。就是从最后一个有叶子结点的结点开始。

2.3 复杂度分析

添加一个定时器的时间复杂度为O(logN)，删除一个定时器的复杂度为O(1)，此外，可以通过辅助数据结构（map或者hashtable来快速索引节点）来加快定时器节点的查找。

三、C++封装实现

接下来将基于C++11设计一个实用的定时器，类设计如下：

#include <queue>#include <unordered_map>#include <time.h>#include <algorithm>#include <arpa/inet.h> #include <functional> #include <assert.h> #include <chrono>using TimeoutCallBack = std::function<void()>;using Clock = std::chrono::high_resolution_clock;   // ns级时钟using MS = std::chrono::milliseconds;using TimeStamp = Clock::time_point;      // 具体时间// 定时器节点struct TimerNode{    int id;    TimeStamp expires;    TimeoutCallBack cb;    bool operator<(const TimerNode& t){ return expires < t.expires;    }};// 定时器管理类class HeapTimer{public:    HeapTimer() { heap_.reserve(64); }    ~HeapTimer() { clear(); } void adjust(int id, int newExpires);    void add(int id, int timeOut, const TimeoutCallBack& cb);    void doWork(int id);    void clear();    void tick();    void pop();    int GetNextTick();private:    void del_(size_t i);    void siftup_(size_t i);    bool siftdown_(size_t index, size_t n);    void SwapNode_(size_t i, size_t j);private:    std::vector<TimerNode> heap_;    std::unordered_map<int, size_t> ref_;  // key：节点id, value：数组索引 };

类成员函数具体实现如下：

#include "heaptimer.h"void HeapTimer::siftup_(size_t i) {    assert(i >= 0 && i < heap_.size());    size_t j = (i - 1) / 2;    while(j >= 0){ if(heap_[j] < heap_[i])     break; SwapNode_(i, j); i = j; j = (i - 1) / 2;    }}// false：不需要下滑  true：下滑成功bool HeapTimer::siftdown_(size_t index, size_t n){    assert(index >= 0 && index < heap_.size());    assert(n >= 0 && n <= heap_.size());    size_t i = index;    size_t j = i * 2 + 1;  // 先标记i的左子节点    while(j < n){ if(j + 1 < n && heap_[j + 1] < heap_[j]) // 得到左右子节点的较小者     j ++; if(heap_[i] < heap_[j])     break; SwapNode_(i, j); i = j; j = i * 2 + 1;    }    return i > index;}void HeapTimer::SwapNode_(size_t i, size_t j) {    assert(i >= 0 && i < heap_.size());    assert(j >= 0 && j < heap_.size());    std::swap(heap_[i], heap_[j]);    ref_[heap_[i].id] = i;    ref_[heap_[j].id] = j;}void HeapTimer::pop() {    assert(!heap_.empty());    del_(0);}void HeapTimer::clear() {    ref_.clear();    heap_.clear();}/* 删除指定位置的结点 */void HeapTimer::del_(size_t index) {    assert(!heap_.empty() && index >= 0 && index < heap_.size());    /* 将要删除的结点换到队尾，然后调整堆 */    size_t i = index;    size_t n = heap_.size() - 1;    assert(i <= n);    if(i < n) { SwapNode_(i, n); if(!siftdown_(i, n)) {     siftup_(i); }    }    /* 队尾元素删除 */    ref_.erase(heap_.back().id);    heap_.pop_back();}/* 调整指定id的结点 */void HeapTimer::adjust(int id, int timeout) {    assert(!heap_.empty() && ref_.count(id) > 0);    heap_[ref_[id]].expires = Clock::now() + MS(timeout);;    siftdown_(ref_[id], heap_.size());}void HeapTimer::add(int id, int timeOut, const TimeoutCallBack& cb){    assert(id >= 0);    size_t i;    if(ref_.count(id) == 0){ // 新元素，堆尾插入，调整堆 i = heap_.size(); ref_[id] = i; heap_.push_back({id, Clock::now() + MS(timeOut), cb}); siftup_(i);    }    else{ // 已存在，调整堆 i = ref_[id]; heap_[i].expires = Clock::now() + MS(timeOut); heap_[i].cb = cb; if(!siftdown_(i, heap_.size())){     siftup_(i); }    }}/* 删除指定id结点，并触发回调函数 */void HeapTimer::doWork(int id){    assert(id >= 0);    if(heap_.empty() || ref_.count(id) == 0) return; size_t i = ref_[id];    TimerNode node = heap_[i];    node.cb();    del_(i);}// 处理超时节点void HeapTimer::tick() {    if(heap_.empty()) return; while(!heap_.empty()){ TimerNode node = heap_.front(); if(std::chrono::duration_cast<MS>(node.expires - Clock::now()).count() > 0)     break; node.cb(); pop();    }}int HeapTimer::GetNextTick(){    tick();    size_t res = -1;    if(!heap_.empty()){ res = std::chrono::duration_cast<MS>(heap_.front().expires - Clock::now()).count(); if(res < 0)     res = 0;    }    return res;}

四、具体应用

4.1 网络连接定时检测

本文所给出的时间堆实现用于HttpServer中，主要负责网络事件的定时检测，使用逻辑如下：
在这里插入图片描述

4.2 技术参考

https://www.cnblogs.com/WindSun/p/11444446.html
https://github.com/hjlogzw

时间堆原理详解及C++11实现

一、背景