网站专题欣赏,网站制作技术有哪些,中铁建设集团有限公司电话号码,wordpress不显示某个栏目一.向下调整建堆
1.二叉树层数与总节点个数关系
层数一定时#xff0c;在二叉树节点个数最大的情况下#xff0c;二叉树为满二叉树#xff0c;如下图所示#xff0c;可以清晰地看到在满二叉树中第h层有2^(h-1)个节点#xff0c;总节点N就等于一个等比数列的求和#xf…一.向下调整建堆
1.二叉树层数与总节点个数关系
层数一定时在二叉树节点个数最大的情况下二叉树为满二叉树如下图所示可以清晰地看到在满二叉树中第h层有2^(h-1)个节点总节点N就等于一个等比数列的求和运用等比数列求和公式可以得到N 2^h - 1 当然还得考虑节点最少的情况此时第h-1层仍是满节点的第h层只有一个节点此时可以使用上述公式得到h-1层满二叉树总节点为2^(h-1) - 1个再加上第h层的1个节点总节点N 2^h-1个 2.单次向下调整的时间复杂度 由最终结论可以看出无论是节点最多还是最少的情况h与N关系的量级都是logN,同时h可以表示单次向下调整的最大次数-1那么单次向下调整的时间复杂度就是logN
3.向下调整总次数
在这篇文章里【数据结构】二叉树-堆_数据结构树可以有三个子树吗-CSDN博客介绍了向下调整算法的思想就是从最后一个节点的父节点开始依次进行向下调整直到最后从下标为0的根节点向下调整完毕那么这个总的调整次数是多少这同样是能够计算出的。
从最后一个节点的父节点开始向下调整即从h-1层开始该层的每个节点向下调整最多调整1次第h-2层最多调整2次如此直到第1层需要h-1次那么每层对应的最多调整次数乘上每层的节点数就是最多情况下需要的调整次数了。该数列是等差比数列使用错位相减法可以得出结论过程如下图所示 注最后一层不需要调整调整次数为0故不需要考虑是否是满二叉树的情况该式子都成立
4.时间复杂度ON
注意时间复杂度不能仅是简单的N个数据乘以单次向下调整的时间复杂度为N*logN这是错误的必须列出具体的关系式再来看。
时间复杂度看的是最坏情况此时每个节点的调整次数都是最大。时间复杂度是数据个数N和执行次数T之间的关系那么此时用已知的两个结论二叉树层数与总结点关系的结论用层数h为桥梁建立起T与N的关系为如下时间复杂度舍小取大N层级大于logN取N则时间复杂度为ON
二.向上调整建堆ON*logN
明白了向下调整建堆那么向上调整建堆就很容易了与向下调整同理不过得出的结果是向上调整算法的时间复杂度为ON*logN远远大于向下调整的ON其实这很容易看出向上调整时越往下调整次数越多同时越往下每层的节点也越多多的节点乘以多的调整次数很显然比不过向下调整的 多节点乘以少的调整次数。
下图中使用的是满二叉树时N对应h的结论其实不管使用哪个N对应h的结论都一样因为其量级就为logN最后的结果也是不变的。
