最小堆及其應(yīng)用：時(shí)間堆

• • 最小堆及其應(yīng)用：時(shí)間堆
    • 一、 堆
      • 1. 概念
      • 2. 最小堆的實(shí)現(xiàn)
      • 3. 性質(zhì)
      • 4. 代碼
    • 二、時(shí)間堆
      • 1. 概念簡(jiǎn)述
      • 2. 實(shí)現(xiàn)細(xì)節(jié)
      • 3. 代碼

一、 堆

---

1. 概念

堆是一種經(jīng)過排序的完全二叉樹，其中任一非終端節(jié)點(diǎn)的數(shù)據(jù)值均不大于（或不小于）其左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的值。

其中，兩個(gè)葉子節(jié)點(diǎn)的大小沒有順序。

堆又分為兩種，最大堆、最小堆。由上面的概念我們可以知道：
- 最大堆： 任一非葉子節(jié)點(diǎn)的值均大于其左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的值。
- 最小堆： 任一非葉子節(jié)點(diǎn)的值均小于其左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的值。

（圖為最小堆）

因此，我們可以得到：最大堆的根節(jié)點(diǎn)的值是最大的，最小堆的根節(jié)點(diǎn)的值是最小的。所以在需要最值問題的時(shí)候，我們可以采用堆這種數(shù)據(jù)結(jié)構(gòu)來處理。

---

2. 最小堆的實(shí)現(xiàn)

由于堆是一種經(jīng)過排序的完全二叉樹，因此在構(gòu)建的時(shí)候需要對(duì)新插入的節(jié)點(diǎn)進(jìn)行一些操作以使其符合堆的性質(zhì)。這種操作就是節(jié)點(diǎn)的上濾與下濾。以最小堆為例：

• 上濾: 將當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)相比，如果當(dāng)前節(jié)點(diǎn)的值比較小，就把當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)交換，繼續(xù)前面的比較，知道當(dāng)前節(jié)點(diǎn)的值比父節(jié)點(diǎn)的值大為止。此時(shí)，便符合最小堆的定義。

• 下濾： 將當(dāng)前節(jié)點(diǎn)與其左、右子節(jié)點(diǎn)相比，如果當(dāng)前節(jié)點(diǎn)的值比其中一個(gè)（或兩個(gè)）子節(jié)點(diǎn)的值大，就把當(dāng)前節(jié)點(diǎn)與兩個(gè)子節(jié)點(diǎn)中較小的那個(gè)交換，繼續(xù)前面的比較，知道當(dāng)前節(jié)點(diǎn)的值比兩個(gè)子節(jié)點(diǎn)的值都小為止。此時(shí)，便符合最小堆的定義。

下濾是將堆上面不符合條件的節(jié)點(diǎn)向下移動(dòng)的過程，上濾則是將堆下面不符合條件的節(jié)點(diǎn)向上移動(dòng)的過程。

交換后：

3. 性質(zhì)

• 用數(shù)組模擬堆：對(duì)于第i個(gè)節(jié)點(diǎn)，其左子節(jié)點(diǎn)的位置是2i + 1， 右子節(jié)點(diǎn)的位置是2i + 2。

• 對(duì)于具有N個(gè)節(jié)點(diǎn)的完全二叉樹，其葉子節(jié)點(diǎn)有( N + 1 ) / 2個(gè)，非葉子節(jié)點(diǎn)有N / 2個(gè)。

• 由于在建立最小堆時(shí)，只要保證每個(gè)節(jié)點(diǎn)的值比其左右子節(jié)點(diǎn)都小即可，因此在建立最小堆時(shí)，只要從最下層開始，遍歷前N / 2個(gè)非葉子節(jié)點(diǎn)( [ 0 ~ n/2-1 ] )進(jìn)行下濾即可。（前提是已經(jīng)有數(shù)組，不是每次向數(shù)組后面添加元素；葉子節(jié)點(diǎn)會(huì)由于其父節(jié)點(diǎn)的下濾而變得有序）

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] ) { // 右子節(jié)點(diǎn)較小child++; // 將節(jié)點(diǎn)切換到右子節(jié)點(diǎn)}if( tmp > array[child] ) { // 子樹的根節(jié)點(diǎn)值大于子節(jié)點(diǎn)值array[hole] = array[child];} else { // tmp節(jié)點(diǎn)的值最小，符合break;}}array[hole] = tmp; // 將最初的節(jié)點(diǎn)放到合適的位置 }/* 主函數(shù)用于建立最小堆的示例代碼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() ); }*/

---

二、時(shí)間堆

---

1. 概念簡(jiǎn)述

由于定時(shí)器的觸發(fā)是由于時(shí)間到了，因此只有時(shí)間最短的定時(shí)器會(huì)首先被觸發(fā)，通過這個(gè)原理，我們可以采用最小堆，將按時(shí)間順序排序，堆頂元素是時(shí)間最短的定時(shí)器，因此只要判斷堆頂元素是否被觸發(fā)即可。只有堆頂定時(shí)器的時(shí)間到了，才會(huì)到其他時(shí)間較晚的定時(shí)器的時(shí)間。

---

2. 實(shí)現(xiàn)細(xì)節(jié)

• 堆頂節(jié)點(diǎn)的刪除：將堆頂節(jié)點(diǎn)刪除，就會(huì)留有一個(gè)空位置，因此可以將最后一個(gè)節(jié)點(diǎn)放到堆頂位置，再對(duì)堆頂節(jié)點(diǎn)進(jìn)行下濾，就可以確保構(gòu)成最小堆。

• 使用數(shù)組來模擬堆的實(shí)現(xiàn)，相比于鏈表而言，不僅節(jié)省空間，而且更容易實(shí)現(xiàn)堆的插入、刪除操作。如上面圖片中的最小堆，可以用數(shù)組表示為：

• 由于非葉子結(jié)點(diǎn)有N/2 - 1個(gè)，因此只要保證這些節(jié)點(diǎn)構(gòu)成的子樹具有堆性質(zhì)，就能保證整棵樹具有堆性質(zhì)。（因?yàn)榉侨~子結(jié)點(diǎn)的下濾會(huì)將葉子節(jié)點(diǎn)也變的具有堆性質(zhì)）

1326547

---

3. 代碼

#ifndef _TIMEHEAP_H_ #define _TIMEHEAP_H_#include <iostream> #include <netinet/in.h> #include <time.h>const int BUFFER_SIZE = 64;class HeapTimer;// 用戶數(shù)據(jù)，綁定socket和定時(shí)器 struct client_data {sockaddr_in address;int sock_fd;char buf[BUFFER_SIZE];HeapTimer* timer; };// 定時(shí)器類 class HeapTimer { public: time_t expire; // 定時(shí)器生效的絕對(duì)時(shí)間client_data* user_data; public: HeapTimer( int delay ) {expire = time( NULL ) + delay;}void ( *cb_func ) ( client_data* ); // 定時(shí)器的回調(diào)函數(shù) };class TimeHeap { private: HeapTimer** array; // 堆數(shù)組int capacity; // 堆數(shù)組容量int cur_size; // 堆數(shù)組當(dāng)前包含元素個(gè)數(shù) public: TimeHeap( int cap ); // 構(gòu)造函數(shù)1，初始化大小為cap的空數(shù)組TimeHeap( HeapTimer** init_array, int size, int cap ); // 構(gòu)造函數(shù)2，根據(jù)已有數(shù)組初始化堆~TimeHeap(); public:void percolate_down( int hole ); // 對(duì)堆結(jié)點(diǎn)進(jìn)行下慮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];}// 因?yàn)闀?huì)比較當(dāng)前節(jié)點(diǎn)與子節(jié)點(diǎn)，所以只從最下層遍歷非葉子節(jié)點(diǎn)即可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; }// 對(duì)堆結(jié)點(diǎn)進(jìn)行下濾，確保第hole個(gè)節(jié)點(diǎn)滿足最小堆性質(zhì) 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 ) { // 右子節(jié)點(diǎn)較小child++; // 將節(jié)點(diǎn)切換到右子節(jié)點(diǎn)}if( tmp->expire > array[child]->expire ) { // 子樹的根節(jié)點(diǎn)值大于子節(jié)點(diǎn)值array[hole] = array[child];} else { // tmp節(jié)點(diǎn)的值最小，符合break;}}array[hole] = tmp; // 將最初的節(jié)點(diǎn)放到合適的位置 }// 添加定時(shí)器，先放在數(shù)組末尾，在進(jìn)行上濾使其滿足最小堆 void TimeHeap::add_timer( HeapTimer* timer ) {if( !timer ) {return ;}if( cur_size >= capacity ) {resize(); // 空間不足，將堆空間擴(kuò)大為原來的2倍}int hole = cur_size++;int parent = 0;// 由于新結(jié)點(diǎn)在最后，因此將其進(jìn)行上濾，以符合最小堆for( ; hole > 0; hole = parent ) {parent = ( hole - 1 ) / 2;if( array[parent]->expire > timer->expire ) {array[hole] = array[parent];} else {break;}}array[hole] = timer; }// 刪除指定定時(shí)器 void TimeHeap::del_timer( HeapTimer* timer ) {if( !timer ) {return;}// 僅僅將回調(diào)函數(shù)置空，雖然節(jié)省刪除的開銷，但會(huì)造成數(shù)組膨脹timer->cb_func = nullptr; }// 刪除堆頂定時(shí)器 void TimeHeap::pop_timer() {if( !cur_size ) {return;}if( array[0] ) {delete array[0];array[0] = array[--cur_size];percolate_down( 0 ); // 對(duì)新的根節(jié)點(diǎn)進(jìn)行下濾} }// 從時(shí)間堆中尋找到時(shí)間的結(jié)點(diǎn) void TimeHeap::tick() {HeapTimer* tmp = array[0];time_t cur = time( NULL );while( !cur_size ) {if( !tmp ) {break ;}if( tmp->expire > cur ) { // 未到時(shí)間break;}if( array[0]->cb_func ) {array[0]->cb_func( array[0]->user_data );}pop_timer();tmp = array[0];} }// 空間不足時(shí)，將空間擴(kuò)大為原來的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

總結(jié)

以上是生活随笔為你收集整理的【高性能定时器】时间堆（最小堆）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。