博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
证明:在任一含n个元素的堆中,至多有ceiling(n/(2^(h+1)))个高度为h的节点
阅读量:4558 次
发布时间:2019-06-08

本文共 425 字,大约阅读时间需要 1 分钟。

证明:在任一含n个元素的堆中,至多有ceiling(n/(2^(h+1)))个高度为h的节点

第i(下标为i)个结点无孩子,则2*i > n 得到i > n/2且i=floor(n/2), 此时高度为0的结点个数为ceiling(2^(0+1));--因为小于i的结点+大于i的结点等于n;

i为第一个无孩子的结点,则去掉叶结点后i+1即为余下的堆中的元素个数(因为i为下标,元素个数为i+1)

因此,去掉叶结点后,设第ii个结点无孩子,则,2*ii > i+1 > i,得到ii> i/2 > n/2^2,且ii = floor(n/2^2), 此时高度为1的结点个数小于等于n/2^2=ceiling(2^(1+1);

同理,可得堆中高度为k的结点个数为n/2^(k+1)=ceiling(2^(k+1);

转载于:https://www.cnblogs.com/taotao315/archive/2013/03/11/2953765.html

你可能感兴趣的文章
redis4安装
查看>>
使用命令wsimport构建WebService客户端[转]
查看>>
第八遍:链接详解
查看>>
Qt5.5 使用smtp发邮件的各种坑
查看>>
js奇葩错误 字符串传递问题
查看>>
人之初,性本恶
查看>>
springboot 端口号
查看>>
使用AChartEngine画动态曲线图
查看>>
安卓项目五子棋代码详解(四)
查看>>
urllib 学习一
查看>>
bzoj4196 [Noi2015]软件包管理器——树链剖分
查看>>
kafka源码阅读环境搭建
查看>>
UI设计
查看>>
androidtab
查看>>
Windows Phone 自定义弹出框和 Toast 通知
查看>>
如何生成静态页面的五种方案
查看>>
php 事件驱动 消息机制 共享内存
查看>>
剑指offer 二叉树的bfs
查看>>
LeetCode Maximum Subarray
查看>>
让我们再聊聊浏览器资源加载优化
查看>>