参考答案：

解析：j++
(2)j*=2或j=k*2
(3)j=n+1或break
(4)adjust(i,n)
(5)adjust(1,k-1)

[分析]：
函数adjust(i,n)是把以R[i](1≤i≤┗i/2┛)为根的二叉树调整成堆的函数，假定R[i]的左、右子树已经是堆，程序中的r是在主函数中说明的结构数组，它含有要排序的n个记录。
Void adjust(i,n)
Int i,n；
{
int k,j;
element extr;
extr=r[i];
k=i;
j=2*i;
while(j＜=n)
{if((j＜n)&&(r[j].key＜r[j+ 1].key))
j++;
if(extr.key＜r[j].key)
{
r[k]=r[j];
k=j;
j*=2;
}
else
j=n+1;
}
r[k]=extr;
}
/* 让i从┗i/2 ┛逐步减到1, 反复调用函数adjust, 便完成建立初始堆的过程。堆排序程序heapsort 如下*/
void heapsort(r,n)
list r;
int n;
{
int i,l;
element extr;
for (i=n/2;i＞= 1 ;--i)
adjust(i,n); /*建立初始堆*/
for(k=n;k＞=2;k--)
{
extr=r[1];
r[1]=r[k];
r[k]=extr;
adjust(1,k-1);
}
}
函数heapsoff的第一个for循环建立初始化。没待排序的n个记录组成—棵深度为h的完全二叉树，因此有2h-1＜n≤2h+1-1，即2h≤n＜2h+1。完全二叉树的第i层(设根结点的层次为0)上最多有2i个结点，对每个非叶结点，都要调用过程adjust，同时可能移动结点(向下移动)，第i层上的结点可能要移动的最大距离为h-i，若设向下移动一层花费的时间为c，则第i层2i个结点调整的时间最多为c*(h-i)*2i建立初始堆的全部时间应是：
令j=h-1，则i=h-j，所以有：
对第二个for循环，调用adjust函数n-1次，每次总是由根向下调整，调整的最大距离为log₂n(实际上，调整的距离是逐渐变小的)，所以总的时间不多于c*(n-1)log₂n＝O(log₂n)．堆排序总的时间为：
O(n)+O(nlog₂n)=O(max(n,n log₂n))=O(n log₂n)
算法需要的存储空间是存储n个记录的数组以及少量暂存单元。
堆排序算法是不稳定的。