libevent中的小根堆

libevent中的min-heap，稍有改动。

#include <stdlib.h>
#include <time.h>

using namespace std;
#ifndef NULL
#define NULL 0
#endif

#include long long timestamp() {    struct timeval val;    gettimeofday(&val, NULL);    return val.tv_sec * 1000000LL + val.tv_usec;}

typedef unsigned int uint32;
typedef struct data_ {
    int idx;
    int da;
}data_t;

typedef struct min_heap {
    data_t **p;
    uint32 a, n;
}min_heap_t;

inline void min_heap_init(min_heap_t *s);
inline void min_heap_uninit(min_heap_t *s);
inline int min_heap_reserve(min_heap_t *s, uint32 n);

inline uint32 min_heap_size(min_heap_t *s);

inline int min_heap_push(min_heap_t *s, data_t *data);
inline data_t *min_heap_pop(min_heap_t *s);
inline data_t *min_heap_top(min_heap_t *s);
inline int min_heap_erase(min_heap_t *s, data_t *data);
inline data_t *min_heap_erase(min_heap_t *s, uint32 idx);
inline void min_heap_shift_up(min_heap_t *s, uint32 hole_index, data_t *data);
inline void min_heap_shift_down(min_heap_t *s, uint32 hole_index, data_t *data);

void min_heap_init(min_heap_t *s) {
    s->p = NULL;
    s->n = s->a = 0;
}

void min_heap_uninit(min_heap_t *s) {
    if (s->p) {
        s->n = s->a = 0;
        free(s->p);
    }
}

uint32 min_heap_size(min_heap_t *s) {
    return s->n;
}

int min_heap_push(min_heap_t *s, data_t *data) {
    if (min_heap_reserve(s, s->n+1) < 0) {
        return -1;
    }
    min_heap_shift_up(s, s->n++, data);
    return 0;
}

data_t *min_heap_top(min_heap_t *s) {
    if (s->n) {
        return *s->p;
    }
    return NULL;
}

data_t *min_heap_pop(min_heap_t *s) {
    if (s->n) {
        data_t *d = *s->p;
        min_heap_shift_down(s, 0u, s->p[--s->n]);
        d->idx = -1;
        return d;
    }
    return NULL;
}

int min_heap_erase(min_heap_t *s, data_t *data) {
    if (data->idx > 0 && s->n > 0) {
        data_t *last = s->p[--s->n];
        uint32 parent = (data->idx - 1 ) / 2 ;
        if (s->p[parent]->da > last->da) {
            min_heap_shift_up(s, data->idx, last);
        }
        else {
            min_heap_shift_down(s, data->idx, last);
        }
        data->idx = -1;
        return 0;
    }
    else if (data->idx == 0 && min_heap_pop(s)) {
        return 0;
    }
    return -1;
}

data_t* min_heap_erase(min_heap_t *s, uint32 idx) {
    if (idx > 0 && idx < s->n) {
        data_t *d = s->p[idx];
        data_t *last = s->p[--s->n];
        uint32 parent = (d->idx - 1) / 2;
        if (s->p[parent]->da > last->da) {
            min_heap_shift_up(s, d->idx, last);
        }
        else {
            min_heap_shift_down(s, d->idx, last);
        }
        d->idx = -1;
        return d;
    }
    else if (idx == 0) {
        return min_heap_pop(s);
    }
    return NULL;
}

int min_heap_reserve(min_heap_t *s, uint32 n) {
    if (s->a < n) {
        data_t **p;
        uint32 a = s->a ? s->a*2:8;
        if (a < n) {
            a = n;
        }
        p = (data_t**)realloc(s->p, a * sizeof(*p));
        if (p == NULL) {
            return -1;
        }
        s->p = p;
        s->a = a;
    }
    return 0;
}

void min_heap_shift_up(min_heap_t *s, uint32 hole_index, data_t *data) {
    uint32 parent = (hole_index - 1) / 2;
    while (hole_index && s->p[parent]->da > data->da) {
        s->p[hole_index] = s->p[parent];
        s->p[hole_index]->idx = hole_index;
        hole_index = parent;
        parent = (hole_index - 1) / 2;
    }
    s->p[hole_index] = data;
    data->idx = hole_index;
}

void min_heap_shift_down(min_heap_t *s, uint32 hole_index, data_t *data) {
    uint32 min_child = 2 * (hole_index + 1);
    while (min_child <= s->n) {
        if (s->p[min_child]->da > s->p[min_child-1]->da) {
            min_child--;
        }
        if (s->p[min_child]->da >= data->da) {
            break;
        }
        s->p[hole_index] = s->p[min_child];
        s->p[hole_index]->idx = hole_index;
        hole_index = min_child;
        min_child = 2 * (hole_index + 1);
    }
    data->idx = hole_index;
    s->p[hole_index] = data;
}

int main(int argc, char **argv) {

    min_heap_t *s = new min_heap_t;
    printf("heap size:%d\n", min_heap_size(s));
    vector<data_t*> vd;
    long long t = timestamp();
    for (int i = 0; i < 100; i++) {
        data_t *d = new data_t;
        d->da = rand() % 100;
        fprintf(stderr, "i:%d\n", d->da);
        vd.push_back(d);
        min_heap_push(s, d);
    }
    printf("heap size:%d\n", min_heap_size(s));
    for (int i = 0; i < vd.size(); i++) {
        fprintf(stderr, "e:%d\n", min_heap_erase(s, vd[i]->idx)->da);
    }

    printf("%ll\n", timestamp() - t);
    printf("heap size:%d\n", min_heap_size(s));

    return 0;
}