引用
-
[](https://zh.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D “维基百科堆结构”) [堆结构](https://zh.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D “维基百科堆结构”) [维基百科] – https://zh.wikipedia.org/wiki/%E5%A0%86%E7%A9%8D
-
[堆结构素材] – https://github.com/wangzhione/temp/tree/master/code/struct
目录
-
简介
-
堆结构定义
-
堆结构实现
3.1 堆结构创建销毁
3.2 堆结构 push 和 pop
3.3 堆结构 remove
- 堆结构实践
4.1 堆结构接口自测
4.2 堆结构面试小练习
- 总结回顾
正文
1. 简介
堆结构多数人很耳熟, 在 堆排序到 优先级队列, 系统库的 快速查找代码中很容易看见它的身影. 相关的资料比较
丰富, 业务上可用代码模板不多见. 本文重点是学以致用, 带大家从代码维度来观察和理解堆结构的工程实现.
(最小堆也被成为小顶堆, 最大堆也被称为大顶堆)
2. 堆结构定义
#pragma once
#include "struct.h"
//
// heap_t 堆的数据结构
//
typedef struct heap * heap_t;
//
// heap_create - 构建特定规则的初始'小顶'堆
// fcmp : 当 fcmp(起始结点, 待比较结点) // return : 返回创建好的堆对象
//
extern heap_t heap_create(cmp_f fcmp);
extern void heap_delete(heap_t h, node_f fide);
extern int heap_len(heap_t h);
extern void * heap_top(heap_t h);
extern bool heap_push(heap_t h, void * node);
extern void * heap_pop(heap_t h);
//
// heap_remove - 删除堆中索引 i 数据
// h : 堆对象
// i : 索引 i [0, heap_len())
// return : 索引为 i 的堆结点
//
extern void * heap_remove(heap_t h, int i);
extern void * heap_pop_push(heap_t h, void * node);
其中 struct.h 是数据结构辅助头文件, 有心朋友可以尝试复制和拓展
#pragma once #include#include #include #include #include #include #include #include #include #include #include <float.h> #include <string.h> #include #include #ifndef CMP_F #define CMP_F // // cmp_f - 比较行为 > 0 or = 0 or < 0 // : int add_cmp(const void * now, const void * node) // typedef int (* cmp_f)(); #endif//CMP_F #ifndef NEW_F #define NEW_F // // new_f - 构建行为 // : void * rtree_new(void * node) // typedef void * (* new_f)(); #endif//NEW_F #ifndef NODE_F #define NODE_F // // node_f - 销毁行为 // : void list_die(void * node) // typedef void (* node_f)(); #endif//NODE_F #ifndef EACH_F #define EACH_F // // each_f - 遍历行为, node 是内部结点, arg 是外部参数 // : int echo(void * node, void * arg) { return 0; } // typedef int (* each_f)(void * node, void * arg); #endif//EACH_F // // DCODE - DEBUG 模式下的测试宏 // DCODE({ // puts("debug test start ..."); // }); // #ifndef DCODE ifndef NDEBUG define DCODE(code) do code while(0) else define DCODE(code) endif//NDEBUG #endif//DCODE // // PERR - 打印错误信息 // EXIT - 打印错误信息, 并 exit // IF - 条件判断辅助的程序退出宏 // #define PERR(fmt, ...) \ fprintf(stderr, "[%s:%s:%d][%d:%s]"fmt"\n", \ __FILE__, __func__, __LINE__, errno, strerror(errno), ##__VA_ARGS__) #define EXIT(fmt, ...) \ do { \ PERR(fmt, ##__VA_ARGS__); \ exit(EXIT_FAILURE); \ } while(0) #define IF(cond) \ if ((cond)) EXIT(#cond) // // RETURN - 打印错误信息, 并 return 返回指定结果 // val : return 的东西. 填 NIL 标识 return void; // fmt : 双引号包裹的格式化字符串 // ... : fmt 中对应的参数 // return : val // #define RETURN(val, fmt, ...) \ do { \ PERR(fmt, ##__VA_ARGS__); \ return val; \ } while(0) #define NIL #define RETNIL(fmt, ...) \ RETURN(NIL , fmt, ##__VA_ARGS__) #define RETNUL(fmt, ...) \ RETURN(NULL, fmt, ##__VA_ARGS__) #define RETERR(fmt, ...) \ RETURN(-1 , fmt, ##__VA_ARGS__)
3. 堆结构实现
3.1 堆结构创建销毁
#include "heap.h" #define HEAP_INIT_INT (1<struct heap { void ** data; int len; int cap; cmp_f fcmp; }; heap_t heap_create(cmp_f fcmp) { struct heap * h = malloc(sizeof(struct heap)); if (h == NULL) { return NULL; } h->data = malloc(sizeof(void *) * HEAP_INIT_INT); if (h->data == NULL) { free(h); return NULL; } h->cap = HEAP_INIT_INT; h->len = 0; h->fcmp = fcmp; return h; } void heap_delete(heap_t h, node_f fdie) { if (h != NULL) { return; } if (fdie != NULL && h->len > 0) { for (int i = h->len - 1; i >= 0; i--) fdie(h->data[i]); } free(h->data); free(h); }
怎么创建; 怎么销毁; 何时创建; 何时销毁. 销毁决定了这个语言是精细手工生产工具, 还是高效智能生产工具.
3.2 堆结构 push 和 pop
堆结构 push 和 pop 核心在于结点关系的调整. 总结有 堆结点下沉(向下调整)和 堆结点上浮(向上调整).
// down - 堆结点下沉, 从上到下沉一遍 static void down(cmp_f fcmp, void * data[], int len, int x) { void * m = data[x]; for (int i = (x<<1)+1; i < len; i = (x<<1)+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[], int 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 = (x<
Original: https://www.cnblogs.com/life2refuel/p/14886314.html
Author: 喜欢兰花山丘
Title: 数据结构堆
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/590635/
转载文章受原作者版权保护。转载请注明原作者出处！