6.1-1 在高度为h的堆中，元素个数最多和最少分别是多少？
答：最多为2^(h+1)-1个元素，最少为2^h个元素。因为一棵高度为h-1的完全二叉树，有求和M(0~h1)2^i = 2^h-1个元素。那么高度为h的堆中，有至多为高度为h的完全二叉树的元素个数，即:2^(h+1)-1;至少的情况为h-1高度的完全二叉树再加上一个子元素即2^h个元素。
6.1-2 证明：含n个元素的堆的高度为向下取整(lgn)
答：假设n=2^m-1+k (m足够大),也就是说这个堆是由一棵高度为m-1的完全二叉树和k个叶节点组成。这颗树的高度定义为从根元素出发到叶节点最长简单路径上边的数目。肯定是大于等于m的。所以含有n个元素的堆的高度为向下取整(lgn)。
6.1-3 证明：在最大堆的任一子树中，该子树所包含的最大元素在该子树的根节点上。
答：反证法：如果最大元素不在该子树的根节点上，那么这个最大元素的父亲节点一定小于这个最大元素，违背了最大堆的属性和定义。
6.1-4 假设一个最大堆的所有元素都不相同，那么该堆的最小元素应该位于哪里？
答：显而易见是叶节点了。
6.1-5 一个已排好序的数组是一个最小堆吗？
答：是的，数组索引从左往右依次变大，意味着该堆的子元素都比父元素大，是最小堆。
6.1-6 值为<23,17,14,6,13,10,1,5,7,12>的数组是一个最大堆吗？
答：不是，位于第九位的7比位于第四位的6来的大。所以不是一个最大堆。
6.1-7 证明：当用数组表示存储n个元素的堆时，叶节点下标分别为[n/2]+1,[n/2]+2,...n
答：先顺着推：对于这些索引为[n/2]+1,[n/2]+2,...n的数组元素他们的子节点必然是>=2*[n/2]+2大于了数组的长度n越界了，所以他们没有子元素。再逆着推：对于没有子元素的数组元素，意味者2i,2i+1是大于数组的长度n的，所以对于没有子元素的叶节点来说他们的索引范围为[n/2]+1,[n/2]+2,...n
ps：最近一直忙于接入安卓sdk，很少有时间去看算法导论了。。今天白天陪妹子看了场电影——超时空同居，感觉还不错，男主最终选择了善良抛弃了暴富，值得称赞，但从整部片子来看，2018的上海确实充满着利欲熏心的感觉，这也是现在社会的主要基调吧，挺令人遗憾的。深夜给算法导论第六章开个头，顺便试了下新键盘，青轴感觉不错哦。希望下周sdk能够进行顺利，嗯！
网友评论