最小堆定时器

最小堆定时器

一、前言相信大家在网络编程过程中或者查看开源代码中，总是会遇到一些定时器的功能，今天介绍一种常用的定时器，最小堆定时器；二、最小堆

树的基本概念

完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。

满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。

最小堆定义

堆是一颗完全二叉树；

堆中的某个结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值。

堆中每个结点的子树都是堆树

子节点都小于父节点

数组中的任意一个位置i上的元素，其左子节点在位置2i+1上，其右子节点在2i+2上，其父节点则在（i-1）/2上；三、案例一个数组数据为：21，24，31，65，26

以上就是一个简单的最小堆；这里，参考了网上代码，给大家展示一下代码：

time_heap.h

#pragma once

#include

#include

#include

#include

constintBUFFER_SIZE=64;

classheap_timer;

//用户数据，绑定socket和定时器

structclient_data

{

sockaddr_inaddress;

intsockfd;

charbuf[BUFFER_SIZE];

heap_timer*timer;

};

//定时器

classheap_timer

{

public:

heap_timer(intdelay)

{

expire=time(NULL)+delay;

}

public:

time_texpire;//定时器生效绝对时间

void(*cb_func)(client_data*);//定时器回调函数

client_data*user_data;//客户端数据

};

//时间堆

classtime_heap

{

public:

//构造之一：初始化一个大小为cap的空堆

time_heap(intcap);

//构造之二：用已用数组来初始化堆

time_heap(heap_timer**init_array,intsize,intcapacity);

//销毁时间堆

~time_heap();

//添加定时器timer

intadd_timer(heap_timer*timer);

//删除定时器timer

voiddel_timer(heap_timer*timer);

//获得顶部的定时器

heap_timer*top()const;

//删除顶部的定时器

voidpop_timer();

//心跳函数

voidtick();

//堆是否为空

boolempty()const;

//最小堆的下操作，

//确保堆数组中认第hole个节点作为根的子树拥有最小堆性质

voidpercolate_down(inthole);

//将堆数组容量扩大1倍

voidresize();

private:

heap_timer**array;//堆数组

intcapacity;//堆数组的空量

intcur_size;//堆数组当前包含元素个数

};

time_heap.cpp

#include "time_heap.h"

time_heap::time_heap(intcap):capacity(cap),cur_size()

{

//创建数组

array=newheap_timer*[capacity];

if(!array)

{

fprintf(stderr,"init heap faild");

return;

}

for(inti=;i

{

array[i]=NULL;

}

}

time_heap::time_heap(heap_timer**init_array,intsize,intcapacity):

capacity(capacity),cur_size(size)

{

if(capacity

{

fprintf(stderr,"init ");

}

//创建堆数组

array=newheap_timer*[capacity];

if(!array)

{

fprintf(stderr,"init heap_timer failed");

return;

}

for(inti=;i

{

array[i]=NULL;

}

//初始化堆数组

if(size!=)

{

for(inti=;i

array[i]=init_array[i];

for(inti=(cur_size-1)/2;i>=;--i)

{

percolate_down(i);

}

}

}

time_heap::~time_heap()

{

for(inti=;i

{

deletearray[i];

}

delete[]array;

}

inttime_heap::add_timer(heap_timer*timer)

{

if(!timer)

return-1;

//如果堆数组不够大，在扩充一倍

if(cur_size>=capacity)

{

resize();

}

////新插入一个元素，当前堆大小加1, hole是新建空穴的位置

inthole=cur_size++;

intparent=;

//对从空穴到根节点的路径上的所有节点执行上虑操作

for(;hole>;hole=parent)

{

parent=(hole-1)/2;

if(array[parent]->expireexpire)

{

break;

}

array[hole]=array[parent];

}

array[hole]=timer;

return;

}

voidtime_heap::del_timer(heap_timer*timer)

{

if(!timer)

return;

timer->cb_func=NULL;

}

heap_timer*time_heap::top()const

{

if(empty())

{

returnNULL;

}

returnarray[];

}

voidtime_heap::pop_timer()

{

if(empty())

{

return;

}

if(array[])

{

deletearray[];

//将原来的堆顶元素替换为堆数组中最后一个元素

array[]=array[--cur_size];

//对新的堆顶元素执行以下操作

percolate_down();

}

}

voidtime_heap::tick()

{

heap_timer*tmp=array[];

time_tcur=time(NULL);

//循环处理定时器

while(!empty())

{

if(!tmp)

{

break;

}

//如果堆顶定时没有到期，则退出循环

if(tmp->expire>cur)

{

break;

}

//否则执行堆顶定时器中的回调函数

if(array[]->cb_func)

{

array[]->cb_func(array[]->user_data);

}

//删除堆顶元素，同时生成新的堆顶定时器

pop_timer();

tmp=array[];

}

}

voidtime_heap::percolate_down(inthole)

{

heap_timer*tmp=array[hole];

intchild=;

for(;((hole*2)+1)

{

child=hole*2+1;

if(childexpire

array[child]->expire)

{

++child;

}

if(array[child]->expireexpire)

{

array[hole]=array[child];

}

else

{

/* code */

break;

}

}

array[hole]=tmp;

}

voidtime_heap::resize()

{

heap_timer**tmp=newheap_timer*[2*capacity];

for(inti=;i

{

tmp[i]=NULL;

}

if(!tmp)

{

fprintf(stderr,"resize() faild");

return;

}

capacity=2*capacity;

for(inti=;i

{

tmp[i]=array[i];

}

delete[]array;

array=tmp;

}

booltime_heap::empty()const

{

if(empty())

returnNULL;

returnarray[];

}

想了解学习更多C++后台服务器方面的知识，请关注：微信公众号：====C++后台服务器开发====