Exercises
6.1-1
最多为2h+1-1个，因为堆是只有最低层未满的二叉树，所以最少也会有2h个元素。
6.1-2
根据h≤lgn<h+1,所以h等于lgn的向下取整。
6.1-3
因为最大堆的每一层的元素都必定比下一层的大，所以子树所包含的最大元素在该子树的根节点上。
6.1-4
最小元素必然在最大堆的页节点上。
6.1-5
是
6.1-6
显然不是。
6.1-7
显然。
6.2-1.略。
6.2-2.略，运行时间应该与MAX-HEAIFY的运行时间一样。
6.2-3.没什么变化。
6.2-4.同样没什么变化。
6.2-5.C/C++ Code:
void Max_Heapify(int a[],int i){ int largest; while(true){ if((2*i+1)<=n&&a[i]<a[2*i+1]) largest=2*i+1; else largest=i; if(2*i+2<=n&&largest<a[2*i+2]) largest=2*i+2; if(largest!=i){ int temp=a[i]; a[i]=a[largest]; a[largest]=temp; i=largest; } else break; }; }
6.2-6
最坏情况就是从根节点一直调用到叶子节点，也就是树高lgn，所以最坏运行时间为Ω(lgn)。
6.3-1.略。
6.3-2
调用MAX-HEAPIFY的条件是该结点的左右子树都是最大堆，如果从1到A.length/2递增调用，是无法保证此条件的。
6.3-3
6.4-1.略。
6.4-2
初始化：i=A.length，子数组A[1...A.length]是一个包含数组A[1...n]中第A.length小元素的最大堆，必然包含，字数组A[i+1...n]是空的，所以包含0个最大元素。
保持：假设当第i次迭代开始之前，子数组A[1...i+1]是一个包含数组A[1...n]中第i+1小元素的最大堆，子数组A[i...n]包含了数组A[1...n]中已经排序的一个n-i-1个最大元素。此时A[1]为A[1...i+1]中的最大值，为A[1...n]中第i+1小的元素，交换A[1],A[i],此时将A.heap-size减1，A[1...i]中就是一个包含数组A[1...i]中第i小元素的最大堆，而子数组A[i+1]必然是一个排序好的序列。
终止：终止时i=1，此时堆为空，A[2..n]中包含了数组最大的n-1个元素，显然成立。
6.4-3
无论是升序还是降序，都是Θ(nlgn)。
6.4-5.略。
6.4-6.略。
6.5-1.略。
6.5-2.略。
6.5-3.略。
6.5-4
设置为﹣∞可以对所有的节点进行插入操作，因为该插入操作调用的HEAP-INCEASE-KEY必需保证增加的key大于原来的值。
6.5-5
初始化：在第一次循环开始前，A[1...A.heap-size]一定满足最大堆的性质，所以只有A[i]增加到key之后A[i]和A[parent(i)]之间不满足堆的性质。
保持：假设中间一次循环开始前满足该性质，交换A[i]和A[parent(i)]之后，只有可能导致A[parent(i)]和A[parent(parent(i))]不满足堆的性质，所以下一次循环也就满足该满足该循环不变式终止：i=1或A[i]>A[parent(i)]时循环终止，这两个条件都不会破坏最大堆的性质，应为A[i]没有parent，而A[i]>A[parent(i)]并不破坏堆的性质。
6.5-6
利用插入排序的性质，可以很容易得出结论。
6.5-7
保证先进入的元素的key值大于后进入key即可实现队列。栈的话反之。
6.5-8
对以i为根的堆提取最大值即可。
6.5-9
从该堆中提取一个元素，之后再将提取元素的链表中找出下一个元素插入到堆中。
Thingking Problems
6-1
a.不总是一样的。
b.max-heap-insert的时间复杂度是O(lgn)，for循环使其调用n次，所以该算法时间复杂度是O(nlgn)。
6-2
a.根据归纳可知，结点i的孩子的范围是[(i-1)d+2,id+2]，同理，其父结点的下标为(n-d)/2+1。
b.logdn=O(lgn)。
c.d.e.
同2叉堆基本一致，只是选取在max-heapify中选取最大的时候，要与所有孩子进行比较。
6-3
a.略。
b.根据Young式矩阵的性质，很容易得出。
c.与堆的操作非常类似，不过堆比较的是左右孩子，Young矩阵比较的是右面和下面的元素。最坏情况就是从左上角的元素一直交换到右下角的元素，这样交换次数为m-1+n-1=m+n-1，所以为O(m+n)。T(p)≤T(max(m,n))+Θ(1)。
d.与堆的插入操作同样类似，与上方和左方的元素进行比较，时间复杂度是O(m+n)。
e.先构造Young氏矩阵，对n2个元素进行插入操作，每个插入操作的时间复杂度是O(n+n)，所以需O(n3)，之后再取每个元素的最小值，复杂度也同样是O(n3)。这样即可排序。
f.与右面与下面元素依次比较大小即可，来决定是向右走还是向左走，最坏情况就是从左上角走到右下角。共需进行O(m+n)次比较。