引言 - 数据结构堆
堆结构都很耳熟, 从堆排序到优先级队列, 我们总会看见它的身影. 相关的资料太多了,
堆 - 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. 这就是堆节点调整的无上奥妙. 随后