1 #include <iostream> 2 using std::cout; 3  4 void max_heapify(int *a,int len,int i) 5 { 6     //以0开始的数组，左孩子为2i+1，右孩子为2i+2 7     int l=2*i+1,r=2*i+2,largest; 8  9     //选出最大值，记录其指针到largest10     if(l<len && a[l]>a[i])largest=l;11     else largest=i;12     if(r<len && a[r]>a[largest])largest=r;13     if(largest!=i)14     {15         {int temp=a[i];a[i]=a[largest];a[largest]=temp;}16 17         //节点有变化，所以要对有变化的节点进行heapify18         //因为heapify是在其子节点heapify之后进行的19         max_heapify(a,len,largest);20     }21 }22 void bulid_max_heap(int *a,int len)23 {24     //len/2,len/2+1...是叶节点，不用heapify25     for(int i=len/2;i>=0;i--)max_heapify(a,len,i);26 }27 void heapsort(int *a,int len)28 {29     int temp;30     bulid_max_heap(a,len);31     for(int i=len-1;i>=1;i--)32     {33         //将堆顶（最大值）放到数组尾34         {temp=a[0];a[0]=a[i];a[i]=temp;}35         36         //数组长度-1，heapify根节点，又成为了最大堆37         len--;38         max_heapify(a,len,0);39     }40 }41 42 43 int main()44 {45     int a[]={12,8564,445,56,8,54,6,4,5,4};46     heapsort(a,10);47     for(int i=0;i<10;i++)cout<<a[i]<<"  ";48 49     return 0;50 }