转载

一个用宏实现的堆模板

昨天在写定时器管理的时候，要用到一个最小堆，C++一个Map就搞定了，C的话就只能自己动手丰衣足食了。

作为数据结构的实现，可复用性十分重要。比如这里的堆结构，至少要满足两点，首先堆中的元素类型不被限制，其次堆的性质(min堆, max堆)不被限制。这两点在C++里可以使用模板实现，而C中一般使用宏或者void*指针实现，我这里用的是宏。关于堆的操作，实现了堆的初始化、堆排序、堆的任意节点删除、以及PUSH与POP堆元素这几个较为主要的操作。

堆的核心操作是向上调整及向下调整。所谓上调整，是指前N个节点已构成一个堆，将第N+1个节点调整到堆的合适位置；而下调整是指以该节点的两个孩子为根已构成两个堆，将该节点调整到堆的合适位置。

堆的其它操作都基于这两个操作。初始化堆是从第N/2个节点到第一个节点依次进行下调整（上调整也能初始化堆，但方向相反）；堆排序就是不断POP后将最后一个节点放到第一个节点并进行下调整；堆节点删除是用最后一个节点替换删除节点并根据其值与父节点关系决定是上调整还是下调整；而PUSH和POP操作更是直接对应了上调整与下调整。

堆实际上就是一棵满二叉树，它的好处是不用记录树的父子关系，因为x节点的左右儿子分别是(x 2)和(x 2+1)，而父节点就是(x/2)，我的代码中就是用满二叉树结构来保存堆的。另外，需要注意的是PUSH操作中用户要保证空间足够（只有这一个操作会增加堆使用空间）。详细代码如下：

#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)

接下来看一下如何使用这些宏。这里的comp函数用过sort或者qsort的童鞋应该很熟悉，类似于比较的回调函数，可以是函数也可以是宏，它决定了堆的性质，比如我们要定义一个元素为Integer的最小堆，可以 #define CMP_INT(a,b) ((a) < (b)) ，再将CMP_INT作为comp参数即可，而如果我们想将它改为最大堆，只要把 < 改成 > 就可以了。

以下测试程序先将数组build成最小堆并排序，之后又将数组build成最大堆并进行一些操作；最后使用堆保存了rectangle结构体，并且遵循先按w(宽)再按h(长)排序的规则。

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 sort
1 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 elemet
16 14 10 9 8 7 4 3 2 1 
16 14 7 9 8 1 4 3 2 

//pop the first elemet
14 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}