知识卡片
堆容器用数组表达隐式树
本章Heap有size、compare、destroy和tree四字段。tree指向应用数据地址的数组,父子关系由下标隐式表示,结构里没有root节点指针或每项左右链接。
结构图:
classDiagram
class Heap {
int size
int (*compare)(const void* a, const void* b)
void (*destroy)(void* data)
void** tree
}
class HeapAPI["堆公开函数组(非类型)"] {
heap_init(Heap* heap, compare, destroy) void
heap_destroy(Heap* heap) void
heap_insert(Heap* heap, const void* data) int
heap_extract(Heap* heap, void** data) int
}
HeapAPI ..> Heap : 维护数组和局部堆序
init回调是字段所示同型函数指针简写,size入口是宏。本实现没有独立capacity字段,每次插入/提取会调整数组大小,这一表示选择也影响实际成本。
174正文漏提compare初始化,但02899实际heap_init明确heap->compare=compare,另写destroy、size=0、tree=NULL。只需固定字段写入为O(1),不对全部潜在元素预分配空间。
178及02895 heap_size(heap)=((heap)->size),不遍历数组。02898–02903完整heap.c含私有父子下标宏、init/destroy/insert/extract全部实读,上浮/下沉成本与realloc分开,输出失败语义已记录。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 堆容器用数组表达隐式树
- · heap_init
- · heap_size
原书出处 · 3 处
- · 查看原书依据
此结构体包含4个成员:size指明堆中结点的个数;compare与destroy是用于封装传入heap_init的函数的指针;tree是堆中存储结点的数组。 示例10-1:堆的头文件
- · 查看原书依据
初始化过程比较简单,它将size成员设置为0;将destroy成员指向destroy;然后将tree指针设置为NULL。 heap_init的时间复杂度为O(1),因为初始化堆的几个步骤都能在固定时间内完成。
- · 查看原书依据
size来获得。 其时间复杂度为O(1)。因为遍历过程是一个运行时间固定的运算过程。 示例10-2:堆的实现
参考来源
- 位置:《算法精解:C语言描述》第10章《堆的实现与分析》(spine1310;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1277.html;u173-ch10-006)。
- 结论依据:173完整四字段正文、02895完整heap.h及02899–02903实际数组realloc实读,未把逻辑树画成实际BiTree节点继承。
- 原始内容:此结构体包含4个成员:size指明堆中结点的个数;compare与destroy是用于封装传入heap_init的函数的指针;tree是堆中存储结点的数组。 示例10-1:堆的头文件
- 位置:《算法精解:C语言描述》第10章《heap_init》(spine1310;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1277.html;u174-ch10-006)。
- 结论依据:174正文漏提compare初始化,但02899实际heap_init明确heap->compare=compare,另写destroy、size=0、tree=NULL。只需固定字段写入为O(1),不对全部潜在元素预分配空间。
- 原始内容:初始化过程比较简单,它将size成员设置为0;将destroy成员指向destroy;然后将tree指针设置为NULL。 heap_init的时间复杂度为O(1),因为初始化堆的几个步骤都能在固定时间内完成。
- 位置:《算法精解:C语言描述》第10章《heap_size》(spine1314;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1281.html;u178-ch10-006)。
- 结论依据:178及02895 heap_size(heap)=((heap)->size),不遍历数组。02898–02903完整heap.c含私有父子下标宏、init/destroy/insert/extract全部实读,上浮/下沉成本与realloc分开,输出失败语义已记录。
- 原始内容:size来获得。 其时间复杂度为O(1)。因为遍历过程是一个运行时间固定的运算过程。 示例10-2:堆的实现