2014-03-13-heap.md

layout	title	category	description	tags
post	堆	数据结构	Heap...	heap 堆 数据结构

Heap是一种数据结构，内核里经常使用，例如优先级队列，进程调度等等。Heap是一种完全二叉树结构，但是使用数组表示。其操作性能与树的高度成正比。

堆的基本性质

堆用数组表示，由于是完全二叉树，则满足：

1. t/2表示父节点。
2. t*2表示左孩子。
3. t*2+1表示右孩子。

这里简单的讲解一下创建、插入元素和弹出元素的操作。

CODE

创建一个堆：

typedef int heap_elem_t;

typedef struct heap_t
{
    int size;
    int capacity;
    heap_elem_t *elems;
    int (*cmp)(const heap_elem_t*, const heap_elem_t*);
}heap_t;

heap_t*
heap_create(const int capacity,
            int(*cmp)(const heap_elem_t*, const heap_elem_t*)){
    //给堆分配内存
    heap_t *h = (heap_t*)malloc(sizeof(heap_t));
    h->size = 0;
    h->capacity = capacity;
    //堆的元素本质上是数组
    h->elems = (heap_elem_t*)malloc(sizeof(heap_elem_t));
    h->cmp = cmp;
    return h;
}

插入一个元素，基本思想是在数组的最后插入一个元素，然后和父亲比较，如果比父亲小，则交换数据。然后从最后一个元素往前重复之前的和父亲比较的逻辑。

void
heap_push(heap_t *h, const heap_elem_t e){
    if(h->size == h->capacity) {
        heap_elem_t *tmp = (heap_elem_t*)realloc(h->elems,
            h->capacity*2*sizeof(heap_elem_t));
        h->elems = tmp;
        h->capacity *= 2;
    }

    h->elems[h->size] = e;
    h->size++;
    heap_shift_up(h, h->size-1);
}

其中heap_shift_up方法如下：

void
heap_shift_up(const heap_t *h, const int start){
    // 当前元素
    int j = start;
    // 父元素
    int i = (j-1)/2;
    const heap_elem_t tmp = h->elems[start];

    //除非到根节点
    while(j>0){
        // 比较父元素
        if(h->cmp(&(h->elems[i]), &tmp)<=0){
            // 如果当前元素比父元素小，则直接返回
            break;
        } else {
            // 如果当前元素比父元素大，交换元素
            h->elems[j] = h->elems[i];
            // 继续往上重复逻辑
            j = i;
            i = (i-1)/2;
        }
    }

    h->elems[j] = tmp;
}

堆中弹出逻辑如下，基本思想为把第0个元素弹出，用最后一个元素替换。也就是把最后一个元素拿到跟节点，然后从根节点向下比较。

void
heap_pop(heap_t *h){
    h->elems[0] = h->elems[h->size - 1];
    h->size--;
    heap_shift_down(h, 0);
}

其中heap_shift_down逻辑如下：

void
heap_shift_down(const heap_t *h, const int start){
    // 父节点
    int i = start;
    int j;
    const heap_elem_t tmp = h->elems[start];

    // j为子节点中的右孩子，如果不小于size
    for(j=2*i+1; j<h->size; j=2*j+1) {

        // 如果没有找到最下层的最右节点并且
        // 比较两个孩子的大小，找到小的那个一
        if(j<(h->size -1)&&
            h->cmp(&(h->elems[j]), &(h->elems[j+1]))>0){
            j++;
        }

        // 和子节点比较，如果比子节点小，退出
        if(h->cmp(&tmp, &(h->elems[j]))<=0) {
            break;
        } else {
            // 如果比子节点大，交换元素
            h->elems[i] = h->elems[j];
            // 继续往下查找
            i = j;
        }
    }

    h->elems[i] = tmp;
}

完整代码看这个GIST。