知识卡片

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

完全二叉形状可隐式存入数组

理解等级:中级

二叉堆按层从左到右填满,最后一层可不满但连续靠左。这样层级遍历的节点可密集放进0至n−1的数组位置,不需每节点保存左右链接。

零起点下标i的左孩子在2i+1、右孩子在2i+2,i>0时父亲为⌊(i−1)/2⌋;孩子下标超出n−1表示不存在,根没有父亲。最后节点就是数组n−1,便于在插入/提取时维护形状。

02889把11节点表示为[25,20,22,17,19,10,12,15,7,9,18]。非完全树沿同样编号可能留下大量空位,不能把任意稀疏树密集排进数组后仍套这组父子公式。

183十层树前九层满、末层只有最右节点,按零起点占到2¹⁰−2=1022,需要1023槽;有效512节点,中间511空位,利用率约50%。指数按层数理解,稀疏形状使隐式编号浪费空间。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      水平遍历的方式连续存储到一个数组中(见第9章)。假设有一个零索引数组,这表示数组中处于位置i处的节点,其父结点位于i-1/2处,计算中要忽略(i-1)/2的小数部分。其左结点和右结点分别位于2i+1和2i+2位置上。这样的组织结构对于堆来说非常重要,因为通过它我们能迅速地定位堆的最后一个结点:最后一

    • · 查看原书依据

      1022(在一个零索引数组中)。第9层最右边的那个结点在空间中的位置为29-2=510。那么,为了存放这棵树需要总共1023个位置,而其中(1022-510)-1=511位置都是空的。所以数组的空间利用率只有50%。 问:假设我们用一个优先队列存放一些已经由应用程序预先设定好顺序的任务。如果系统不断

    参考来源

    - 位置:《算法精解:C语言描述》第10章《堆的描述》(spine1308;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1275.html;u171-ch10-004)。 - 结论依据:171全部表示段及02889树/数组逐项实读,括号明确修正正文i−1/2歧义;183稀疏树反例后续并入。 - 原始内容:水平遍历的方式连续存储到一个数组中(见第9章)。假设有一个零索引数组,这表示数组中处于位置i处的节点,其父结点位于i-1/2处,计算中要忽略(i-1)/2的小数部分。其左结点和右结点分别位于2i+1和2i+2位置上。这样的组织结构对于堆来说非常重要,因为通过它我们能迅速地定位堆的最后一个结点:最后一 - 位置:《算法精解:C语言描述》第10章《问与答》(spine1319;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1286.html;u183-ch10-004)。 - 结论依据:183十层树前九层满、末层只有最右节点,按零起点占到2¹⁰−2=1022,需要1023槽;有效512节点,中间511空位,利用率约50%。指数按层数理解,稀疏形状使隐式编号浪费空间。 - 原始内容:1022(在一个零索引数组中)。第9层最右边的那个结点在空间中的位置为29-2=510。那么,为了存放这棵树需要总共1023个位置,而其中(1022-510)-1=511位置都是空的。所以数组的空间利用率只有50%。 问:假设我们用一个优先队列存放一些已经由应用程序预先设定好顺序的任务。如果系统不断