《算法导论》第六章 堆排序 维护堆的性质 为啥最坏情况发生在树的最底层恰好半满的时候
1.因为最大堆是一个类似完全二叉树的数组，左右子树的高度最多相差1，所以在子树的高度较高的一边时执行的次数可能越多。递归的时候，二分成左子树和右子树，当树的最底层半满时，左子树最大程度的占据树的比例，所以此时是最坏情况。2.2/3n的推导，设最底层半满，最底层元素个数为x个，那么整棵树元素有2x*2-1-x = 3x-1 = n个，左子树有(2x-1-1)/2+x = 2x-1个，联立可得左子树2n/3-1/3\u0026lt;2/3n个人温馨提示：这种问题还是不要在里问比较好，一般没人看到。
推荐阅读
- |常信院在第六届中国国际互联网+大赛中再夺金
- 江苏：前列腺癌发病率位列恶性肿瘤第六位
- |江苏省全国精神文明建设先进光荣榜
- 国内油价|国内油价或迎年内第六次上调 再现“二连涨”局面
- 自学C，有如《C Primer Plus》第六版一类较经典的书推荐吗
- 小蚊子聊车|10月份紧凑型轿车销量排行，卡罗拉被挤到第六，逸动闯入前十
- |传承美德 弘扬良好家风 第六届“苏州十佳最美家庭”揭晓
- 自动化|第六批市级示范智能车间评选开始，须符合11个条件
- 兴化市|兴化市举办第六届创意创业大赛
- 实验学校|第六届市青少年科技创新市长奖评选，这些孩子和学校榜上有名……