# 一个用宏实现的堆模板

`#define RSHIFT(x) ((x) >> 1)#define LSHIFT(x) ((x) << 1)#define LCHILD(x) LSHIFT(x)#define RCHILD(x) (LSHIFT(x)|1)#define HEAP_FIX_UP(heap, type, pos, size, comp) do {      /    int pos_ = (pos);                                      /    type val_ =  (heap)[pos_];                             /    while (pos_ > 1 && comp(val_, (heap)[RSHIFT(pos_)])) { /        (heap)[pos_] = (heap)[RSHIFT(pos_)];               /        pos_ = RSHIFT(pos_);                               /    }                                                      /    (heap)[pos_] = val_;                                   /} while (0)#define HEAP_FIX_DOWN(heap, type, pos, size, comp) do {    /    int pos_ = (pos);                                      /    type val_ = (heap)[pos_];                              /    while (LCHILD(pos_) <= (size)) {                       /        int npos_ = LCHILD(pos_);                          /        npos_ += (RCHILD(pos_) <= (size) &&                /            comp((heap)[npos_+1], (heap)[npos_]) ? 1 : 0); /        if (comp(val_, (heap)[npos_]))                     /            break;                                         /        (heap)[pos_] = (heap)[npos_];                      /        pos_ = npos_;                                      /    }                                                      /    (heap)[pos_] = val_;                                   /} while (0)#define HEAP_INIT(heap, type, size, comp) do {             /    int ind_ = (size) / 2 + 1;                             /    while (--ind_)                                         /        HEAP_FIX_DOWN(heap, type, ind_, size, comp);       /} while (0)#define HEAP_SORT(heap, type, size, comp) do {             /    int size_ = (size);                                    /    while (size_ > 0) {                                    /        type tmp_ = (heap)[1];                             /        (heap)[1] = (heap[size_]);                         /        (heap)[size_--] = tmp_;                            /        HEAP_FIX_DOWN(heap, type, 1, size_, comp);         /    }                                                      /} while (0)#define HEAP_DELETE(heap, type, pos, size, comp) do {      /    (heap)[pos] = (heap)[(size)--];                        /    if (pos > 1 && comp((heap)[pos], (heap)[RSHIFT(pos)])){/        HEAP_FIX_UP(heap, type, pos, size, comp);          /    } else {                                               /        HEAP_FIX_DOWN(heap, type, pos, size, comp);        /    }                                                      /} while (0)#define HEAP_PUSH(heap, type, size, elm, comp) do {        /    (heap)[++(size)] = (elm);                              /    HEAP_FIX_UP(heap, type, size, size, comp);             /} while (0)#define HEAP_POP(heap, type, size, comp)                   /    HEAP_DELETE(heap, type, 1, size, comp)`

`typedef struct rectangle_ {    int w, h;}rectangle;rectangle rect[10] = {    {0, 0},    {3, 7},{15, 32},{3, 5},{6, 13},    {13,6},{21, 4},{14, 3},{13, 1}};int rectsize = 8;#define COMP_RECT(ra, rb) /    ((ra).w < (rb).w || (ra).w==(rb).w && (ra).h < (rb).h)int array[20]= {0, 4,1,3,2,16,9,10,14,8,7};int hsize = 10;#define COMP_INT_MIN(a, b) ((a) < (b))#define COMP_INT_MAX(a, b) ((a) > (b))void print_array_rect(rectangle *rect, int start, int end) {    int i;    for (i = start; i <= end; i++) {        printf("{%d,%d} ", rect[i].w, rect[i].h);        if (i == end) printf("/n");    }}void print_array_int(int *array, int start, int end) {    int i;    for (i = start; i <= end; i++) {        printf("%d ", array[i]);        if (i == end) printf("/n");    }}int main (int argc, char *argv[]) {    /* init a Min Heap */    HEAP_INIT(array, int, hsize, COMP_INT_MIN);    print_array_int(array, 1, hsize);    /* use heap sort a integer array */    HEAP_SORT(array, int, hsize, COMP_INT_MIN);    print_array_int(array, 1, hsize);    /* reinit the array to be a Max Heap, and try delete an element */    HEAP_INIT(array, int, hsize, COMP_INT_MAX);    print_array_int(array, 1, hsize);    HEAP_DELETE(array, int, 3, hsize, COMP_INT_MAX);    print_array_int(array, 1, hsize);    /* pop the max element of the Max Heap */    HEAP_POP(array, int, hsize, COMP_INT_MAX);    print_array_int(array, 1, hsize);    /* insert a new element into the Max Heap */    HEAP_PUSH(array, int, hsize, 6, COMP_INT_MAX);    print_array_int(array, 1, hsize);    /* heap operation on the rectangle struct */    HEAP_INIT(rect, rectangle, rectsize, COMP_RECT);    print_array_rect(rect, 1, rectsize);    HEAP_SORT(rect, rectangle, rectsize, COMP_RECT);    print_array_rect(rect, 1, rectsize);    return 0;}`

`//build min heap and sort1 2 3 4 7 9 10 14 8 16 16 14 10 9 8 7 4 3 2 1 //build max heap and delete the 3rd elemet16 14 10 9 8 7 4 3 2 1 16 14 7 9 8 1 4 3 2 //pop the first elemet14 9 7 3 8 1 4 2 //push a new elemet (6)14 9 7 6 8 1 4 2 3 //build a min heap of rect and sort it{3,5} {6,13} {3,7} {13,1} {13,6} {21,4} {14,3} {15,32} {21,4} {15,32} {14,3} {13,6} {13,1} {6,13} {3,7} {3,5}`