堆排序程序中的小于等于号问题

做堆排序问题时遇到一个bug，调试了很久才发现原因，是一个 小于号和小于等于号 的问题，在递归时的边界没考虑周全。代码用java写的，拿出来分析下，首先是网上比较多的使用大于号控制边界的程序：

 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("  " );     }     } 

堆排序结果：
0, 1, 2, 3, 4, 5, 6 是正确的（输出的一些中间结果就不给了）

我的代码是参考《算法导论》中的伪代码，在MaxHeapFixUp函数中红色字体的部分使用了小于等于号

 if(lchild<=heapsize && a[lchild]>a[i]){ //lchild<=heapsize 为何出错？             largest = lchild;         }else{             largest = i;         }  if(rchild<=heapsize && a[rchild]>a[largest]){             largest = rchild;         } 

结果就出错了：5, 2, 3, 0, 4, 1, 6,

下面是算法导论中伪代码（第一版，P75），可以看到这里也是用的 小于等于号

当时我是按照《算法导论》中思路写的，所以并不知道是小于等于号出的问题，只能把中间步骤输出来找原因。由于输入的数组已经是一个大根堆，所以建堆过程没有问题。建堆之后，要把堆顶元素跟数组末尾元素交换，同时使堆长度减一，再对剩余的堆进行调整。下面的输出就反映了堆调整的过程：

黄色部分的第一行表示执行了 heapSort 函数中的 swap 语句，将大根堆堆顶的元素 5 与数组末尾元素 1 交换（此时6已经不再堆中，1为最后一个数）

第二行表示执行 MaxHeapFixUp( int [] a, int i, int heapsize) 函数后的结果，首先对 i=0 节点进行进行调整，在0号节点和它的子节点1和2中找到最大值并放到根节点0处。显然这里A[2]=4是A[0],A[1],A[2]中最大的，所以把A[0]跟A[2]交换。数组由 1, 3, 4, 0, 2, 5, 6 变为 4, 3, 1, 0, 2, 5, 6 ，这一步是没有问题的。

第三行是继续执行 MaxHeapFixUp( int [] a, int i, int heapsize) 函数后的结果，因为A[2]是一个根节点，在上一步中它的值发生了变化，所以需要重新调整以A[2]为根的堆。A[2]的孩子分别是A[5]和A[6]，貌似我们要继续比较A[2],A[5],A[6]的值找到最大值并将其跟A[2]交换。但是问题来了，在第一行的输出中，我们将A[5]=5放到了数组的最后，也就是将它排出了堆，也就是说 此后在堆的操作中不能再涉及到A[5]了。

然而，很不幸，在代码中，我写到

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

在这步中 lchild=5，heapsize=5 ，就把A[5]的值和A[2]交换了，得到 4, 3, 5, 0, 2, 1, 6

所以改成小于等于号后扩大了堆的范围，将刚被移出堆的数（移出的数已就完成了部分排序）又拉进来了，这样刚排好的序又给打乱了，结果就出现错误了。

解决方法：

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;     } 

这样其实更加合理，因为在heapSort函数中第一次执行 swap(A,0,i) 时，已经将A[0]=6和A[n-1]=1互换，也就是把堆顶元素A[0]=6移出了堆， 此时堆的大小应该是6，在数组中下标是1到5，i-1=5 。

《算法导论》中伪代码认为数组下标从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("  " );     }     }