知识卡片

结构图卡 · 3613.d.5 · 生成模型:未记录

堆容器用数组表达隐式树

理解等级:中级

本章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 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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:堆的实现