服务器程序通常管理着众多的定时事件，因此有效地组织这些定时事件，使之能在预期的时间点被触发且不影响服务器的主要逻辑，对于服务器的性能有着至关重要的影响。 本篇主要讨论的是时间堆的设计。在利用最小堆结构来设计定时方案前，我们先来了解一下什么是最小堆。
1.概念 最小堆是指每个节点的值都小于或等于其子节点的值的完全二叉树。如下图，就是一个具有6个元素最小堆：
2.最小堆的插入操作 树的基本操作是插入节点和删除节点，最小堆的插入操作步骤如下： 以插入X元素为例 1）在树的下一个空闲位置创建一个空穴，如果X可以放在空穴中而不破坏堆序，则插入完成，否则就执行2）上虑操作；
2）上虑操作即交换空穴和它的父节点上的元素。不断执行该过程，直到X可以被放入空穴，则插入操作完成。
例如向上图的最小堆中插入值为14的元素，步骤如下：
3.最小堆的删除操作 最小堆的删除操作指的是删除其根节点上的元素，并且不破坏堆序性质。最小堆的删除操作步骤如下： 1）首先在根节点出创建一个空穴；
2）因为删除了根节点，现在堆少了一个元素，因此我们可以把堆的最后一个元素X移动到该堆的某个地方。如果X可以被放入空穴，则删除操作完成，否则就执行3）下虑操作；
3）下虑操作即交换空穴和它的两个儿子节点中的较小者。不断执行该过程，直到X可以被放入空穴，则删除操作完成。
例如对上图的最小堆执行删除操作，步骤如下：
4.最小堆的数组表示 由于最小堆是一种完全二叉树，所以我们可以用数组来组织其中的元素。比如上图的最小堆可用可用数组表示如下：
对于数组中的任意一个位置 i 上的元素，其左儿子节点在位置 2i + 1 上，其右儿子节点在位置 2i + 2 上，其父节点则在位置 [ ( i - 1) / 2 ] ( i > 0 ) 上。与用链表来表示堆相比，用数组表示堆不仅节省空间，而且更容易实现堆的插入、删除等操作。
5.最小堆的初始化操作 假设我们已经有一个包含N个元素的数组，现在要把它初始化为一个最小堆。那么最简单的方法是：初始化一个空堆，然后将数组中的每个元素插入该堆中。不过这样做的效率偏低。实际上，我们只需要对数组中的第 0 ~ [ (N - 1) / 2 ] 个元素执行下虑操作，即可确保该数组构成一个最小堆。这是因为对包含N个元素的完全二叉树而言，它具有 [ (N - 1) / 2 ] 个非叶子节点，这些非叶子节点正是该完全二叉树的第 0 ~ [ (N - 1) / 2 ] 个节点。我们只要确保这些非叶子节点构成的子树都具有堆序性质，整个树就具有堆序性质。
设计定时器的一种思路如下： 将所有定时器中超时时间最小的一个定时器的超时值作为心搏间隔。这样，一旦心搏函数 tick 被调用，超时时间最小的定时器必然到期，我们就可以在 tick 函数中处理该定时器。然后，再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔，如此反复，就实现了较为精确的定时。
最小堆很适合处理这种定时方案，我们称用最小堆实现的定时器为时间堆。
一种时间堆的实现如下：
#include <iostream> #include <netinet/in.h> #include <time.h> using std::exception; #define BUFFER_SIZE 64 // 前向声明定时器类 class heap_timer; // 用户数据，绑定socket和定时器 struct client_data { sockaddr_in address; int sockfd; char buf[ BUFFER_SIZE ]; heap_timer* timer; }; // 定时器类 class heap_timer { public: heap_timer( int delay ) { expire = time( NULL ) + delay; } public: time_t expire; // 定时器生效的绝对时间 void (*cb_func)( client_data* ); // 定时器的回调函数 client_data* user_data; // 用户数据 }; // 时间堆类 class time_heap { public: // 构造函数之一，初始化一个大小为cap的空堆 time_heap( int cap ) throw ( std::exception ) : capacity( cap ), cur_size( 0 ) { array = new heap_timer* [capacity]; if ( ! array ) { throw std::exception(); } for( int i = 0; i < capacity; ++i ) { array[i] = NULL; } } // 构造函数之二，用已有数组来初始化堆 time_heap( heap_timer** init_array, int size, int capacity ) throw ( std::exception ) : cur_size( size ), capacity( capacity ) { if ( capacity < size ) { throw std::exception(); } array = new heap_timer* [capacity]; if ( ! array ) { throw std::exception(); } for( int i = 0; i < capacity; ++i ) { array[i] = NULL; } if ( size != 0 ) { // 初始化堆数组 for ( int i = 0; i < size; ++i ) { array[ i ] = init_array[ i ]; } // 对数组中的第 [ (N - 1) / 2 ] ~ 0 个元素执行下虑操作 for ( int i = (cur_size-1)/2; i >=0; --i ) { percolate_down( i ); } } } // 析构函数，销毁时间堆 ~time_heap() { for ( int i = 0; i < cur_size; ++i ) { delete array[i]; } delete [] array; } public: // 添加目标定时器，时间复杂度为O(logN) void add_timer( heap_timer* timer ) throw ( std::exception ) { if( !timer ) { return; } // 当前堆数组容量不够则将其扩大一倍 if( cur_size >= capacity ) { resize(); } int hole = cur_size++; // hole是新建空穴的位置 int parent = 0; // 对从空穴到根节点的路径上的所有节点执行上虑操作 for( ; hole > 0; hole=parent ) { parent = (hole-1)/2; if ( array[parent]->expire <= timer->expire ) { break; } array[hole] = array[parent]; } array[hole] = timer; } // 删除目标定时器，时间复杂度为O(1) void del_timer( heap_timer* timer ) { if( !timer ) { return; } // 延迟销毁，仅仅将目标定时器的回调函数设置为空 // 这将节省真正删除该定时器造成的开销，但这样做容易使堆数组膨胀 timer->cb_func = NULL; } // 获得堆顶的定时器 heap_timer* top() const { if ( empty() ) { return NULL; } return array[0]; } // 删除堆顶的定时器 void pop_timer() { if( empty() ) { return; } if( array[0] ) { delete array[0]; // 将堆顶元素替换为堆数组中最后一个元素，并对它进行下虑操作 array[0] = array[--cur_size]; percolate_down( 0 ); } } // 心搏函数，执行一个定时器的时间复杂度为O(1) void tick() { heap_timer* tmp = array[0]; time_t cur = time( NULL ); // 循环处理堆中到时的定时器 while( !empty() ) { if( !tmp ) { break; } // 定时器未到期则退出循环 if( tmp->expire > cur ) { break; } // 定时器到期则执行堆顶定时器中的任务 if( array[0]->cb_func ) { array[0]->cb_func( array[0]->user_data ); } // 弹出堆顶元素，同时设置新的堆顶元素 pop_timer(); tmp = array[0]; } } bool empty() const { return cur_size == 0; } private: // 下虑操作函数 void percolate_down( int hole ) { heap_timer* temp = array[hole]; int child = 0; // 当下虑到叶子节点时，循环终止 for ( ; ((hole*2+1) <= (cur_size-1)); hole=child ) { child = hole*2+1; // 空穴的左孩子节点 // 选择两个儿子节点中的较小者 if ( (child < (cur_size-1)) && (array[child+1]->expire < array[child]->expire ) ) { ++child; } // 如果空穴比较小的儿子节点大则交换，否则该元素可以放入空穴 if ( array[child]->expire < temp->expire ) { array[hole] = array[child]; } else { break; } } array[hole] = temp; } // 将堆数组容量扩大一倍 // 创建新数组并将容量扩大一倍，初始化新数组，然后将原内容拷贝过来，并释放原空间 void resize() throw ( std::exception ) { heap_timer** temp = new heap_timer* [2*capacity]; for( int i = 0; i < 2*capacity; ++i ) { temp[i] = NULL; } if ( ! temp ) { throw std::exception(); } capacity = 2*capacity; for ( int i = 0; i < cur_size; ++i ) { temp[i] = array[i]; } delete [] array; array = temp; } private: heap_timer** array; // 堆数组 int capacity; // 堆数组的容量 int cur_size; // 堆数组当前包含的元素个数 };参考资料： 《Linux高性能服务器编程》 游双
