福田网站设计公司,全国城建证书查询,wordpress模板转为emlog,哪个网站可以做验证码兼职最小堆及其应用#xff1a;时间堆 最小堆及其应用#xff1a;时间堆 一、 堆1. 概念2. 最小堆的实现3. 性质4. 代码 二、时间堆1. 概念简述2. 实现细节3. 代码 一、 堆 1. 概念 堆是一种经过排序的完全二叉树#xff0c;其中任一非终端节点的数据值均不大于#xff08;或…最小堆及其应用时间堆 最小堆及其应用时间堆 一、 堆1. 概念2. 最小堆的实现3. 性质4. 代码 二、时间堆1. 概念简述2. 实现细节3. 代码 一、 堆 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( vectorT 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[child1] ) { // 右子节点较小child; // 将节点切换到右子节点}if( tmp array[child] ) { // 子树的根节点值大于子节点值array[hole] array[child];} else { // tmp节点的值最小符合break;}}array[hole] tmp; // 将最初的节点放到合适的位置
}/* 主函数用于建立最小堆的示例代码vectorint 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个因此只要保证这些节点构成的子树具有堆性质就能保证整棵树具有堆性质。因为非叶子结点的下滤会将叶子节点也变的具有堆性质
1326547 3. 代码
#ifndef _TIMEHEAP_H_
#define _TIMEHEAP_H_#include iostream
#include netinet/in.h
#include time.hconst 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[child1]-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
