引言 - 数据结构堆

　　堆结构都很耳熟, 从堆排序到优先级队列, 我们总会看见它的身影. 相关的资料太多了,

堆 - https://zh.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D

无数漂亮的图片接二连三, 但目前没搜到一个工程中可以舒服用的代码库. 本文由此痛点而来.

写一篇奇妙数据结构堆的终结代码. 耳熟终究比不过手热 ->---

对于 heap 接口思考, 我是这样设计

#ifndef _H_HEAP
#define _H_HEAP

//
// cmp_f - 比较行为 > 0 or = 0  or < 0
// : int add_cmp(const void * now, const void * node)
//
typedef int (* cmp_f)();

//
// node_f - 销毁行为
// : void list_die(void * node)
//
typedef void (* node_f)(void * node);

//
// head_t 堆的类型结构
//
typedef struct heap * heap_t;

//
// heap_create - 创建符合规则的堆
// fcmp     : 比较行为, 规则 fcmp() <= 0
// return   : 返回创建好的堆对象
//
extern heap_t heap_create(cmp_f fcmp);

//
// heap_delete - 销毁堆
// h        : 堆对象
// fdie     : 销毁行为, 默认 NULL
// return   : void
//
extern void heap_delete(heap_t h, node_f fdie);

//
// heap_insert - 堆插入数据
// h        : 堆对象
// node     : 操作对象
// return   : void
//
extern void heap_insert(heap_t h, void * node);

//
// heap_remove - 堆删除数据
// h        : 堆对象
// arg      : 操作参数
// fcmp     : 比较行为, 规则 fcmp() == 0
// return   : 找到的堆节点
//
extern void * heap_remove(heap_t h, void * arg, cmp_f fcmp);

//
// heap_top - 查看堆顶结点数据
// h        : 堆对象
// return   : 堆顶节点
//
extern void * heap_top(heap_t h);

//
// heap_top - 摘掉堆顶结点数据
// h        : 堆对象
// return   : 返回堆顶节点
//
extern void * heap_pop(heap_t h);

#endif//_H_HEAP

heap_t 是不完全类型实体指针, 其中 struct heap 是这样设计

#include "heap.h"
#include <stdlib.h>
#include <assert.h>

#define UINT_HEAP       (1<<5u)

struct heap {
    cmp_f   fcmp;       // 比较行为
    unsigned len;       // heap 长度
    unsigned cap;       // heap 容量
    void ** data;       // 数据节点数组
};

// heap_expand - 添加节点扩容
inline void heap_expand(struct heap * h) {
    if (h->len >= h->cap) {
        h->data = realloc(h->data, h->cap<<=1);
        assert(h->data);
    }
}

从中可以看出当前堆结构是可以保存 void * 数据. 其中通过 heap::fcmp 比较行为来调整关系.

有了堆的数据结构定义, 那么堆的创建和销毁业务代码就被无脑的确定了 ~

//
// heap_create - 创建符合规则的堆
// fcmp     : 比较行为, 规则 fcmp() <= 0
// return   : 返回创建好的堆对象
//
inline heap_t 
heap_create(cmp_f fcmp) {
    struct heap * h = malloc(sizeof(struct heap));
    assert(h && fcmp);
    h->fcmp = fcmp;
    h->len = 0;
    h->cap = UINT_HEAP;
    h->data = malloc(sizeof(void *) * UINT_HEAP);
    assert(h->data && UINT_HEAP > 0);
    return h;
}

//
// heap_delete - 销毁堆
// h        : 堆对象
// fdie     : 销毁行为, 默认 NULL
// return   : void
//
void 
heap_delete(heap_t h, node_f fdie) {
    if (NULL == h || h->data == NULL) return;
    if (fdie && h->len > 0)
        for (unsigned i = 0; i < h->len; ++i)
            fdie(h->data[i]);
    free(h->data);
    h->data = NULL;
    h->len = 0;
    free(h);
}

随后将迎接这个终结者堆的全貌. 此刻读者可以先喝口水 : )

 

前言 - 写一段终结代码

　　堆结构中最核心两处就是向下调整和向上调整过程代码

// down - 堆节点下沉, 从上到下沉一遍
static void down(cmp_f fcmp, void * data[], unsigned len, unsigned x) {
    void * m = data[x];
    for (unsigned i = x * 2 + 1; i < len; i = x * 2 + 1) {
        if (i + 1 < len && fcmp(data[i+1], data[i]) < 0)
            ++i;
        if (fcmp(m, data[i]) <= 0)
            break;
        data[x] = data[i];
        x = i;
    }
    data[x] = m;
}

// up - 堆节点上浮, 从下到上浮一遍
static void up(cmp_f fcmp, void * node, void * data[], unsigned x) {
    while (x > 0) {
        void * m = data[(x-1)>>1];
         if (fcmp(m, node) <= 0)
            break;
        data[x] = m;
        x = (x-1)>>1;
    }
    data[x] = node;
}

如何理解其中奥妙呢. 可以这么看, 索引 i 节点的左子树索引为 2i+1, 右子树树索引为 2i+2 = (2i+1)+1.

相反的索引为 i 节点的父亲节点就是 (i-1)/2 = (i-1)>>1. 这就是堆节点调整的无上奥妙.  随后