知识卡片
调整层数不包含重分配成本
二叉堆上浮/下沉在固定比较与交换成本下最多O(log n)步,但本书每次增删还用realloc把指针数组改为恰好所需大小。若重分配需要搬移现有n个地址,就可能有线性复制工作,不能把它无条件当O(1)。
因此该源码不能仅凭树高论证完整插入/提取最坏O(log n),反复逐一重分配还可能积累较大搬移代价。保留几何增长的容量或其他存储方案可提供不同摊还成本,但本实现没有capacity字段或这样的策略。
这里区分的是算法的堆序调整与表示维护,不是在给某个分配器测量耗时;realloc有时可原地完成,也不证明它始终如此。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
重新分配存储空间,以保证树能容纳此结点。新插入的结点将首先放到数组的末尾。此时将破坏堆的固有特性,所以我们必须调整树的结构,对结点进行重新排列(见图10-2)。 图 10-2 将24插入一个最大值堆中 在插入结点时,为了重新排列一棵树,只需要考虑新结点插入的那个分支,因为这是形成堆的局部开始分支。从
参考来源
- 位置:《算法精解:C语言描述》第10章《heap_insert》(spine1312;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1279.html;u176-ch10-008)。
- 结论依据:176/177正文都将其余步骤视为常数,02899–02901明确逐次realloc到size±1;从可能搬移整个指针数组推导成本边界,未测分配器。
- 原始内容:重新分配存储空间,以保证树能容纳此结点。新插入的结点将首先放到数组的末尾。此时将破坏堆的固有特性,所以我们必须调整树的结构,对结点进行重新排列(见图10-2)。 图 10-2 将24插入一个最大值堆中 在插入结点时,为了重新排列一棵树,只需要考虑新结点插入的那个分支,因为这是形成堆的局部开始分支。从