6.1-1在高度为h的堆中，元素个数最多和最少分别是多少？
最少是最底层只有一个叶子结点:2^0+2^1+...+2^(h-1)+1=2^h
最多是这个堆（包括最底层）是一个完全二叉树:2^0+2^1+...+2^(h-1)+2^h=2^(h+1)-1
6.1-2证明：含n个元素的堆的高度为lgn.
设这个堆的高度为h
这个堆的总结点2^0+2^1+...+2^(h-1)+O(2^h)=n 其中1<=O(2^h)<=2^h
所以1+2^h-1<=2^h-1+O(2^h)<=2^h-1+2^h
2^h<=n<=2^(h+1)-1<2^(h+1)
lgn-1<h<lgn
h=向下取整lgn
6.1-3证明：在最大堆的任意子树中，该子树所包含的最大元素在该子树的根结点上。
最大堆的任意子结点作为父结点，都要符合最大堆的性质所以第i个结点
A[PARENT(i)]>=A[i]
6.1-4假设最大堆的所有元素都不相同，那么该堆的最小元素应该位于哪里？
最小元素必然是在最底层或者是没有子结点的次底层。
6.1-5一个已排好序的数组是一个最小堆吗？
可能是最小堆也可能是最大堆。根据堆的定义：堆上的元素是从左向右填充。
如果最顶层根结点是数组中最小元素。那么按照堆的排序方式，满足最小堆的性质，就是最小堆
如果最顶层根结点是数组中最大元素。那么按照堆的排序方式，满足最大堆的性质，就是最大堆
6.1-6值为<23,17,14,6,13,10,1,5,7,12>的数组是一个最大堆吗？
其中6的子结点7是比6这个父结点要大，不满足最大堆的性质。
6.1-7证明：当用数组表示存储n个元素的堆时，叶结点下标分别是n/2+1,n/2+2,...n.
设堆高度为h.
当此堆第h层都被元素填满时，前h-1层最后一个元素是第2^0+2^1+..2^(h-1)=2^h-1
个，那么从最后一层开始才有叶子结点：2^h,2^h+1....2^h+2^h.
2^0+2^1+...+2^h=n =>h=lg(n+1)-1
所以第一个叶子结点2^h=2^(lg(n+1)-1) =(n+1)/2=n/2+1/2
所以叶子结点向下取整n/2+1,向下取整n/2+2,...n
当此堆第h层只有1个元素时，从第h-1层第二个元素开始都是叶子结点。第h-1层第二个元素下标
是2^0+2^1+...+2^(h-2)+2=2^(h-1)+1,那么从第h-1层第二个元素开始的叶子结点：
2^(h-1)+1,2^(h-1)+2....2^h.
2^0+2^1+...+2^(h-1)+1=n =>h=lgn
所以第一个叶子结点2^(h-1)+1=2^(lgn-1)+1=n/2+1
所以叶子结点向下取整n/2+1,向下取整n/2+2,...n
其他情况类似。
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
