```import java.util.*;
public class MaxHeap {
public static int[] heapSort(int[] A, int n) {
// write code here
MakeMaxHeap(A,n-1);
System.out.println("build complete " );
for(int i=n-1;i>=0;i--){ // 不断减小堆的大小
swap(A, 0, i);
for(int ii=0;ii<7;ii++){
System.out.print(A[ii]+", " );
}
System.out.println("swap  "+"A[0] "+" <->"+" A[i]: "+i );
MaxHeapFixUp(A, 0, i);
}
return A;
}
public static void MakeMaxHeap(int[] a, int heapsize)  {
for (int i = (heapsize-1) / 2 ; i >= 0; i--){
MaxHeapFixUp(a, i, heapsize);
}
}
//  从i节点开始调整,heapsize为堆的长度 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
public static void MaxHeapFixUp(int[] a, int i, int heapsize){
int lchild = 2*i+1;
int rchild = 2*i+2;
int largest=-1;
if(
lchild<heapsize
&& a[lchild]>a[i]){ //lchild<=heapsize 为何出错？
largest = lchild;
}else{
largest = i;
}
if(rchild<heapsize && a[rchild]>a[largest]){
largest = rchild;
}
if(largest != i){
swap(a, largest, i);
for(int ii=0;ii<7;ii++){
System.out.print(a[ii]+", " );
}
System.out.println("swap  "+"largest: "+ largest+" <->"+" i: "+i );
MaxHeapFixUp(a,largest,heapsize);//堆发生变化，要递归调用来调整堆
}
for(int ii=0;ii<7;ii++){
System.out.print(a[ii]+", " );
}
System.out.println("heapsize: "+ heapsize );
}
public static void swap(int[] a, int i, int j){
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void main(String[] args){
int[] A = {6,5,4,3,2,1,0};//{0,1,2,3,4,5,6};
int[] a=heapSort(A,7);
System.out.println("堆排序结果：" );
for(int i=0;i<7;i++)
System.out.print(a[i]+", " );
System.out.println("  " );
}
}```

`我的代码是参考《算法导论》中的伪代码，在MaxHeapFixUp函数中红色字体的部分使用了小于等于号`
```if(lchild<=heapsize && a[lchild]>a[i]){ //lchild<=heapsize 为何出错？
largest = lchild;
}else{
largest = i;
}
if(rchild<=heapsize && a[rchild]>a[largest]){
largest = rchild;
}```

build complete
0, 5, 4, 3, 2, 1, 6, swap A[0] <-> A[i]: 6
5, 0, 4, 3, 2, 1, 6, swap largest: 1 <-> i: 0
5, 3, 4, 0, 2, 1, 6, swap largest: 3 <-> i: 1
5, 3, 4, 0, 2, 1, 6, heapsize: 6
5, 3, 4, 0, 2, 1, 6, heapsize: 6
5, 3, 4, 0, 2, 1, 6, heapsize: 6
1, 3, 4, 0, 2, 5, 6, swap A[0] <-> A[i]: 5
4, 3, 1, 0, 2, 5, 6, swap largest: 2 <-> i: 0
4, 3, 5, 0, 2, 1, 6, swap largest: 5 <-> i: 2
4, 3, 5, 0, 2, 1, 6, heapsize: 5
4, 3, 5, 0, 2, 1, 6, heapsize: 5
4, 3, 5, 0, 2, 1, 6, heapsize: 5

if(lchild<=heapsize && a[lchild]>a[i])

1、如果把不等号改成小于号，改成

if(lchild<heapsize && a[lchild]>a[i])

if(rchild<heapsize && a[rchild]>a[largest])

2、为了保持跟《算法导论》一致，而且方便理解，可以保留小于等于号，但是需要修改heapsize的值，在heapSort函数中将MaxHeapFixUp(A, 0, i); 改为 MaxHeapFixUp(A, 0, i-1);

```public static int[] heapSort(int[] A, int n) {
// write code here
MakeMaxHeap(A,n-1);
System.out.println("build complete " );
for(int i=n-1;i>=0;i--){ // 不断减小堆的大小
swap(A, 0, i);
for(int ii=0;ii<7;ii++){
System.out.print(A[ii]+", " );
}
System.out.println("swap  "+"A[0] "+" <->"+" A[i]: "+i );
MaxHeapFixUp(A, 0, i-1);
}
return A;
}```

《算法导论》中伪代码认为数组下标从1开始，而实际的程序中下标是从0开始的，所以这里数组长度虽然为7，但是heapsize的值却是从6开始递减，因此这里需要用i-1而不是i。

```import java.util.*;
public class MaxHeap {
public static int[] heapSort(int[] A, int n) {
// write code here
MakeMaxHeap(A,n-1);
System.out.println("build complete " );
for(int i=n-1;i>=0;i--){ // 不断减小堆的大小
swap(A, 0, i);
for(int ii=0;ii<7;ii++){
System.out.print(A[ii]+", " );
}
System.out.println("swap  "+"A[0] "+" <->"+" A[i]: "+i );
MaxHeapFixUp(A, 0, i-1);
}
return A;
}
public static void MakeMaxHeap(int[] a, int heapsize)  {
for (int i = (heapsize-1) / 2 ; i >= 0; i--){
MaxHeapFixUp(a, i, heapsize);
}
}
//  从i节点开始调整,heapsize为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
public static void MaxHeapFixUp(int[] a, int i, int heapsize){
int lchild = 2*i+1;
int rchild = 2*i+2;
int largest=-1;
if(
lchild<=heapsize
&& a[lchild]>a[i]){ //lchild<=heapsize 为何出错？
largest = lchild;
}else{
largest = i;
}
if(rchild<=heapsize && a[rchild]>a[largest]){
largest = rchild;
}
if(largest != i){
swap(a, largest, i);
for(int ii=0;ii<7;ii++){
System.out.print(a[ii]+", " );
}
System.out.println("swap  "+"largest: "+ largest+" <->"+" i: "+i );
MaxHeapFixUp(a,largest,heapsize);//堆发生变化，要递归调用来调整堆
}
for(int ii=0;ii<7;ii++){
System.out.print(a[ii]+", " );
}
System.out.println("heapsize: "+ heapsize );
}
public static void swap(int[] a, int i, int j){
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void main(String[] args){
int[] A = {6,5,4,3,2,1,0};//{0,1,2,3,4,5,6};
int[] a=heapSort(A,7);
System.out.println("堆排序结果：" );
for(int i=0;i<7;i++)
System.out.print(a[i]+", " );
System.out.println("  " );
}
}```