heap

8.1 堆 - Hello 算法 (hello-algo.com)

  • 这里使用小根堆来实现计时器。
  • 时间堆通常用于优先队列（priority queue）的实现，其中每个元素都包含一个时间戳，并且堆的根节点总是具有最小时间戳的元素。
  • 当剩余时间耗尽时，执行任务。

heaptimer.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#ifndef HEAP_TIMER_H
#define HEAP_TIMER_H

#include <cstddef>
#include <queue>
#include <unordered_map>

#include <algorithm>
#include <chrono>
#include <functional>

#include <arpa/inet.h> //Internet地址转换函数
#include <assert.h>
#include <time.h>
#include <vector>

#include "../log/log.h"

using TimeoutCallBack = std::function<void()>;
using Clock = std::chrono::high_resolution_clock;
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; }
  bool operator>(const TimerNode &t) { return expires > t.expires; }
};

class HeapTimer {
public:
  HeapTimer();

  ~HeapTimer();

  void adjust(int id, int newExpires);

  void add(int id, int timeOus, 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);

  std::vector<TimerNode> heap_;

  std::unordered_map<int, size_t> ref_;
};

#endif

heaptimer.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include "heaptimer.h"


HeapTimer::HeapTimer() 
{ heap_.reserve(64); }

HeapTimer::~HeapTimer() 
{
    clear();
}
//调整指定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);
    if(ref_.count(id) == 0)
    {
        size_t i = heap_.size();
        ref_[id] = i;
        heap_.push_back({id,Clock::now()+ MS(timeOut),cb});
        siftup_(i);
    }
    else
    {
        size_t i = ref_[id];
        heap_[i].expires = Clock::now() + MS(timeOut);
        heap_[i].cb = cb;        //这里与adjust不同，要重新设置回调函数
        if(!siftdown_(i, heap_.size()))
            siftup_(i);
    }
}

void HeapTimer::doWork(int id){
    if(heap_.empty() || ref_.count(id)==0)  return;
    
    size_t i = ref_[id];
    TimerNode node = heap_[i];
    node.cb();
    del_(i);
}

void HeapTimer::clear()
{
    ref_.clear();
    heap_.clear();
}

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();
    }
}

void HeapTimer::pop(){
    assert(!heap_.empty());
    del_(0);
}

//清除超时计时器并返回下一计时器所剩时间
int HeapTimer::GetNextTick()
{
    tick();
    int res = -1;
    //原文类型是size_t(无符号整型),但是若res为负数，则为无穷大，下面的判断就不起作用了
    //注意ssize_t是有符号整型，size_t则是无符号整型
    if(!heap_.empty())
    {
        res =std::chrono::duration_cast<MS>(heap_.front().expires - Clock::now()).count();
       if(res < 0)
    {
        res = 0;
    }
    }
 
    return res;
}

//我们需要确保树是满树，因此我们需要在vector尾部移除这一元素
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);
          //因为节点n的时间肯定是大于等于i的，所以不会将n处要删除的节点替换掉
        if(!siftdown_(i, n)) {
            siftup_(i);
        }
    }
    /* 队尾元素删除 */
    ref_.erase(heap_.back().id);
    heap_.pop_back();
}
//向上调整
void HeapTimer::siftup_(size_t i)
{
    assert(i >= 0 && i < heap_.size());
    size_t j = (i-1)/2;
    while(j >= 0)
    {
        if(heap_[i] > heap_[j]) break;
        SwapNode_(i, j);
        i = j;
        j = (i-1) /2;
    }

}


//向下调整
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 = 2*i + 1;    //左节点
    
    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 = 2*i + 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]);
    //i，j在heap_的位置已经变化
    ref_[heap_[i].id] = i;
    ref_[heap_[j].id] = j;
}