最小堆及其应用：时间堆
一、 堆
1. 概念
堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左子节点和右子节点的值。
其中，两个叶子节点的大小没有顺序。
堆又分为两种，最大堆、最小堆。由上面的概念我们可以知道：
- 最大堆： 任一非叶子节点的值均大于其左子节点和右子节点的值。
- 最小堆： 任一非叶子节点的值均小于其左子节点和右子节点的值。
（图为最小堆）
因此，我们可以得到：最大堆的根节点的值是最大的，最小堆的根节点的值是最小的。所以在需要最值问题的时候，我们可以采用堆这种数据结构来处理。
2. 最小堆的实现
由于堆是一种经过排序的完全二叉树，因此在构建的时候需要对新插入的节点进行一些操作以使其符合堆的性质。这种操作就是节点的上滤与下滤。以最小堆为例：
上滤: 将当前节点与其父节点相比，如果当前节点的值比较小，就把当前节点与父节点交换，继续前面的比较，知道当前节点的值比父节点的值大为止。此时，便符合最小堆的定义。
下滤： 将当前节点与其左、右子节点相比，如果当前节点的值比其中一个（或两个）子节点的值大，就把当前节点与两个子节点中较小的那个交换，继续前面的比较，知道当前节点的值比两个子节点的值都小为止。此时，便符合最小堆的定义。
下滤是将堆上面不符合条件的节点向下移动的过程，上滤则是将堆下面不符合条件的节点向上移动的过程。
交换后：
3. 性质
用数组模拟堆：对于第i个节点，其左子节点的位置是
2i + 1， 右子节点的位置是2i + 2。对于具有N个节点的完全二叉树，其叶子节点有
( N + 1 ) / 2个，非叶子节点有N / 2个。由于在建立最小堆时，只要保证每个节点的值比其左右子节点都小即可，因此在建立最小堆时，只要从最下层开始，遍历前
N / 2个非叶子节点( [ 0 ~ n/2-1 ] )进行下滤即可。（前提是已经有数组，不是每次向数组后面添加元素；叶子节点会由于其父节点的下滤而变得有序）
4. 代码
template< typename T >
void percolate_down( vector<T>& array, int hole, int n ) {
T tmp = array[hole];
int child = 0;
for( ; hole * 2 + 1 < n; hole = child ) {
child = hole * 2 + 1;
if( child < n-1 && array[child] > array[child+1] ) { // 右子节点较小
child++; // 将节点切换到右子节点
}
if( tmp > array[child] ) { // 子树的根节点值大于子节点值
array[hole] = array[child];
} else { // tmp节点的值最小，符合
break;
}
}
array[hole] = tmp; // 将最初的节点放到合适的位置
}
/* 主函数用于建立最小堆的示例代码
vector<int> t { 3, 6, 2, 1, 5, 4, ７ };
int n = t.size();
for( int i = n/2 - 1; i >= 0; i-- ) {
percolate_down( t, i, t.size() );
}
*/
二、时间堆
1. 概念简述
由于定时器的触发是由于时间到了，因此只有时间最短的定时器会首先被触发，通过这个原理，我们可以采用最小堆，将按时间顺序排序，堆顶元素是时间最短的定时器，因此只要判断堆顶元素是否被触发即可。只有堆顶定时器的时间到了，才会到其他时间较晚的定时器的时间。
2. 实现细节
堆顶节点的删除：将堆顶节点删除，就会留有一个空位置，因此可以将最后一个节点放到堆顶位置，再对堆顶节点进行下滤，就可以确保构成最小堆。
使用数组来模拟堆的实现，相比于链表而言，不仅节省空间，而且更容易实现堆的插入、删除操作。如上面图片中的最小堆，可以用数组表示为：
由于非叶子结点有
N/2 - 1个，因此只要保证这些节点构成的子树具有堆性质，就能保证整棵树具有堆性质。（因为非叶子结点的下滤会将叶子节点也变的具有堆性质）
| 1 | 3 | 2 | 6 | 5 | 4 | 7 |
|---|
3. 代码
#ifndef _TIMEHEAP_H_
#define _TIMEHEAP_H_
#include <iostream>
#include <netinet/in.h>
#include <time.h>
const int BUFFER_SIZE = 64;
class HeapTimer;
// 用户数据，绑定socket和定时器
struct client_data {
sockaddr_in address;
int sock_fd;
char buf[BUFFER_SIZE];
HeapTimer* timer;
};
// 定时器类
class HeapTimer {
public:
time_t expire; // 定时器生效的绝对时间
client_data* user_data;
public:
HeapTimer( int delay ) {
expire = time( NULL ) + delay;
}
void ( *cb_func ) ( client_data* ); // 定时器的回调函数
};
class TimeHeap {
private:
HeapTimer** array; // 堆数组
int capacity; // 堆数组容量
int cur_size; // 堆数组当前包含元素个数
public:
TimeHeap( int cap ); // 构造函数1，初始化大小为cap的空数组
TimeHeap( HeapTimer** init_array, int size, int cap ); // 构造函数2，根据已有数组初始化堆
~TimeHeap();
public:
void percolate_down( int hole ); // 对堆结点进行下虑
void add_timer( HeapTimer* timer );
void del_timer( HeapTimer* timer );
void pop_timer();
void tick();
void resize();
};
TimeHeap::TimeHeap( int cap ) : capacity(cap), cur_size(0) {
array = new HeapTimer*[ capacity ];
if( !array ) {
throw std::exception();
}
for( int i = 0; i < capacity; i++ ) {
array[i] = nullptr;
}
}
TimeHeap::TimeHeap( HeapTimer** init_array, int size, int cap ) : cur_size(size), capacity(cap) {
if( capacity < size ) {
throw std::exception();
}
array = new HeapTimer*[ capacity ];
if( !array ) {
throw std::exception();
}
for( int i = 0; i < size; i++ ) {
array[i] = init_array[i];
}
// 因为会比较当前节点与子节点，所以只从最下层遍历非叶子节点即可
for( int i = size/2 - 1; i >= 0 ; i-- ) {
percolate_down( i );
}
}
TimeHeap::~TimeHeap() {
for( int i = 0; i < cur_size; i++ ) {
if( !array[i] ) {
delete array[i];
}
}
delete[] array;
}
// 对堆结点进行下滤，确保第hole个节点满足最小堆性质
void TimeHeap::percolate_down( int hole ) {
HeapTimer* tmp = array[hole];
int child = 0;
for( ; hole * 2 + 1 < cur_size; hole = child ) {
child = hole * 2 + 1;
if( child < cur_size-1 && array[child]->expire > array[child+1]->expire ) { // 右子节点较小
child++; // 将节点切换到右子节点
}
if( tmp->expire > array[child]->expire ) { // 子树的根节点值大于子节点值
array[hole] = array[child];
} else { // tmp节点的值最小，符合
break;
}
}
array[hole] = tmp; // 将最初的节点放到合适的位置
}
// 添加定时器，先放在数组末尾，在进行上滤使其满足最小堆
void TimeHeap::add_timer( HeapTimer* timer ) {
if( !timer ) {
return ;
}
if( cur_size >= capacity ) {
resize(); // 空间不足，将堆空间扩大为原来的2倍
}
int hole = cur_size++;
int parent = 0;
// 由于新结点在最后，因此将其进行上滤，以符合最小堆
for( ; hole > 0; hole = parent ) {
parent = ( hole - 1 ) / 2;
if( array[parent]->expire > timer->expire ) {
array[hole] = array[parent];
} else {
break;
}
}
array[hole] = timer;
}
// 删除指定定时器
void TimeHeap::del_timer( HeapTimer* timer ) {
if( !timer ) {
return;
}
// 仅仅将回调函数置空，虽然节省删除的开销，但会造成数组膨胀
timer->cb_func = nullptr;
}
// 删除堆顶定时器
void TimeHeap::pop_timer() {
if( !cur_size ) {
return;
}
if( array[0] ) {
delete array[0];
array[0] = array[--cur_size];
percolate_down( 0 ); // 对新的根节点进行下滤
}
}
// 从时间堆中寻找到时间的结点
void TimeHeap::tick() {
HeapTimer* tmp = array[0];
time_t cur = time( NULL );
while( !cur_size ) {
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];
}
}
// 空间不足时，将空间扩大为原来的2倍
void TimeHeap::resize() {
HeapTimer** tmp = new HeapTimer*[ capacity * 2 ];
for( int i = 0; i < 2 * capacity; i++ ) {
tmp[i] = nullptr;
}
if( !tmp ) {
throw std::exception();
}
capacity *= 2;
for( int i = 0; i < cur_size; i++ ) {
tmp[i] = array[i];
}
delete[] array;
array = tmp;
}
#endif