程序员经验分享-hwhale

堆的节点总数n和叶结点数目的关系 (CLRS习题 6.1-7)

2023-10-30

来自算法导论 CLRS的一个习题。Chapter 6 Heap Sort.  Exercise6.1-7

 

Show that, with the array representationfor storing an n-element heap, the leaves are the nodes indexed by ⌊n/2⌋ + 1, ⌊n/2⌋ + 2, . . . , n.

 

首先用一个例子来验证，如图1所示，


非叶节点有20+21+22=1+2+4=7个，叶节点有K+1 (23=8)个。共有15个节点，叶结点开始于第8个，即第 [15/2]+1个，满足结论“叶结点开始于[n/2]+1”


然后开始证明，分为两种情况，完全二叉树和不完全二叉树。

证明之前先清楚高度的定义。一个节点的高度就是从这个节点到叶结点的路径包含的边的数目，树(包括二叉树，堆)的高度被定义为根节点的高度。


(1)如果是完全二叉树

如果是完全二叉树，假设非叶节点有K(20+21+22=1+2+4=7)个，叶节点有K+1 (23=8)个。

假设完全二叉树的高度为h，则

非叶子节点的数目20+21+22

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Math

DataStructureAlgorithm

堆的节点总数n和叶结点数目的关系 (CLRS习题 6.1-7) 的相关文章

  • RNG 技术的可移植性和可重复性

    我可以使用两种方法之一来创建一个伪随机数序列 该序列具有两个重要特征 1 它可以在不同的机器上重现 2 该序列永远不会重复范围内的数字 直到所有数字都被发出 我的问题是 这两种方法在可移植性 操作系统 Python 版本等 方面是否存在潜在

  • Math.Sin、Math.Cos 和 Math.Tan 精度以及正确显示它们的方法

    我正在用 C 编写一个计算器 textBoxResult是一个文本框 我在其中显示数字 recount是以度为单位获取角度并以弧度为单位返回的函数 我的角度是从texBoxInput public double recount int nu

  • 为什么 Math.Atan(Math.Tan(x)) != x？

    如果 tan x y 并且 atan y x 为什么 Math Atan Math Tan x x 我正在尝试计算 x 例如 tan 2 x 3 5 so atan tan 2 x 3 atan 5 等等 但我已经尝试过 double d

  • 线性问题和非线性问题之间的区别？点积和核技巧的本质

    核技巧将非线性问题映射为线性问题 我的问题是 1 线性问题和非线性问题的主要区别是什么 这两类问题的差异背后的直觉是什么 核技巧如何帮助在非线性问题上使用线性分类器 2 为什么点积在这两种情况下如此重要 Thanks 当人们说到分类问题的线

  • 如何计算正切和副法线？

    谈谈OpenGL着色语言 GLSL 中的凹凸贴图 镜面高光之类的东西 I have 顶点数组 例如 0 2 0 5 0 1 0 2 0 4 0 5 法线数组 例如 0 0 0 0 1 0 0 0 1 0 0 0 世界空间中点光源的位置 例如

  • 使用浏览器内的 JS 数值求解三角方程[关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 给定变量值s v and h 并给定一个库 例如数字 js http www numericjs com index php我怎样才能用数

  • 如何对“2-1”这样的字符串进行数学计算以产生“1”？

    我只是想知道 PHP 是否有一个函数可以接受像这样的字符串2 1并产生它的算术结果 或者我必须手动执行此操作explode 获取算术运算符左侧和右侧的值 我知道这个问题很老了 但我昨晚在寻找不太相关的东西时遇到了它 而且这里的每个答案都很糟

  • 求截头棱锥体/截棱锥体横截面的边长

    如何找到横截面的边长 如图所示 下图 横截面 红色 截头锥体 截棱锥体 我知道顶部和底部的边长 以及底部的高度 截锥体和到横截面的距离 此外我还知道 顶部和底部底座平行 并且顶部和底部的中心 底部底座直接位于彼此之上 比例是线性的 因此只需

  • 如何在Python中获得更精确的十进制值[重复]

    这个问题在这里已经有答案了 from math import sqrt a 1e 8 b 10 c 1e 8 x1 b sqrt b 2 4 a c 2 a x2 b sqrt b 2 4 a c 2 a print x1 format x

  • 如何计算具有较大中间值的总和

    我想计算 for n m两个值都是 1000 以内的整数 最终结果是一个不大于 1000 的数字n但中间值对于 python 来说太大了 无法处理 你怎么解决这个问题 我将函数定义如下 from scipy misc import comb

  • Python 中的 C 指针算术

    我正在尝试将一个简单的 C 程序转换为 Python 但由于我对 C 和 Python 都一无所知 这对我来说很困难 我被 C 指针困住了 有一个函数采用 unsigned long int 指针并将其值添加到 while 循环中的某些变量

  • 为什么斐波那契堆被称为斐波那契堆？

    The 斐波那契堆 http en wikipedia org wiki Fibonacci heap数据结构的名称中有 斐波那契 一词 但数据结构中似乎没有任何内容使用斐波那契数 根据维基百科文章 斐波那契堆的名称来自于运行时间分析中使用

  • 计算 Adamic-Adar 的快速算法

    我正在研究图形分析 我想计算一个 N N 相似度矩阵 其中包含每两个顶点之间的 Adamic Adar 相似度 为了概述 Adamic Adar 让我从以下介绍开始 给定邻接矩阵A无向图的G CN是两个顶点的所有公共邻居的集合x y 两个顶

  • 判断一个点是否在直角三角形内

    我一直想知道最简单的方法来确定一个点是否位于三角形内 或者在这种情况下 判断一个点是否位于对角线切成两半的矩形内 假设我有一个 64x64 像素的矩形 对于这个矩形 如果传递的点位于矩形的左上角 我想返回 TRUE 值 否则返回 FALSE

  • 生成随机数背后的数学（崩溃游戏 BTC Casino）

    我正在开发一款基于网络的游戏 其中有多个迷你游戏 我们坚持还添加一个在赌博界非常流行的崩溃游戏 然而 我们一直在努力理解生成随机 几乎不可预测 数字的概念 大多数赌博网站都会提供哈希值等来证明数字未被篡改 我们真的不需要这个 因为我们的游戏

  • Excel - 确定排列的奇偶性

    我正在处理一个 Excel 工作表 需要确定大小数字的垂直数组的奇偶校验N 该数组包含来自的每个数字1 to N每一次正好一次 在这种情况下 奇偶校验被定义为将加扰数组转换为从小到大排序的数组所需的交换次数 例如 数组 3 1 2 4 具有

  • C# 中的反转数

    有没有一种简单的方法可以用函数反转 C 中的数字 我正在使用 XNA 我想告诉我的程序 如果我的 变量 超过某个数字 它必须反转它的值 重点是提供反弹效果 if ballPosition X gt screenWidth Invert th

  • 在 C 中如何安全地找到 2 个有符号整数之间的绝对差？

    绝对差是两个数字之间差的绝对值 假设我有 2int变量 x and y 我想找到绝对差异 一个简单的解决方案是 unsigned diff abs x y 然而 如果发生溢出 这些会调用未定义的行为并给出不正确的结果 例如x is INT

  • 占据花车的地板

    我发现了两种在 Python 中占据发言权的方法 3 1415 1 and import math math floor 3 1415 第一种方法的问题是它返回一个浮点数 即3 0 第二种方法感觉很笨拙而且太长 在 Python 中是否有替

  • 围绕二维坐标系中的特定点缩放

    Below is an image my coordinate system 我想做的是 我想开始围绕画布中的特定点进行缩放 缩放工作正常 但我的问题是我不知道如何计算缩放时移动画布的量 请注意 我我没有使用canvas scale 我只是

随机推荐

热门标签