知识卡片

普通读书笔记卡 · 3613.d.6 · 生成模型:未记录

新堆项沿插入路径上浮

理解等级:中级

插入先把新地址放到数组末尾,保持完全树形状;它可能比父亲优先,因此从末尾沿父路径比较,若新项更优就交换地址并继续上移,直到父亲已不低于它或到根。其他分支原本的堆序没有被新插入破坏,不需重排全数组。

02896在原最大堆加入24:末尾下标11的父为下标5的10,交换;再与下标2的22交换;最后停在根25下面,原10下移到末尾。交换的是数据地址,不是深层复制应用对象。

上浮最多跨O(log n)层,但完整函数还先realloc;应与下面的存储调整成本分开分析。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      数组的末尾。此时将破坏堆的固有特性,所以我们必须调整树的结构,对结点进行重新排列(见图10-2)。 图 10-2 将24插入一个最大值堆中 在插入结点时,为了重新排列一棵树,只需要考虑新结点插入的那个分支,因为这是形成堆的局部开始分支。从新结点开始,将结点向树的上方层层移动,比较每个子结点和它的父结

    参考来源

    - 位置:《算法精解:C语言描述》第10章《heap_insert》(spine1312;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1279.html;u176-ch10-007)。 - 结论依据:176全文、02896全部三阶段与02900实际while/swap/size++实读,跟踪24→10→22路径,未执行。 - 原始内容:数组的末尾。此时将破坏堆的固有特性,所以我们必须调整树的结构,对结点进行重新排列(见图10-2)。 图 10-2 将24插入一个最大值堆中 在插入结点时,为了重新排列一棵树,只需要考虑新结点插入的那个分支,因为这是形成堆的局部开始分支。从新结点开始,将结点向树的上方层层移动,比较每个子结点和它的父结