堆，就是一颗完全二叉树，除了，最后一个行可能不是满的，其他层都是满的
要想进行堆排序，需要知道，最后一个非叶子节点的下标，这里我使用数组，下标从0开始，公式就是(len/2)-1,len就是数组的长度，其实最后一个非叶子节点就是最后一个叶子节点的父节点，最后一个叶子节点下标是len-1,他的父节点就是[(len-1)-1]/2=(len/2)-1
具体下图所示：
这是一个10个大小的堆，用数组下标标识出来的
堆排序，就是对这个堆进行排序
1，首先，我要建立一个堆，就是一个数组a
2，我要对堆进行调整，建立一个大顶堆，把最大的元素，放到堆顶，同时把每一个非叶子节点下的树都调成一个大顶堆（父大于子）
3，调换位置，将堆顶元素和最后一个元素进行调换
4，然后将剩余的len-1个元素进行堆调整，然后调换，然后将剩余的len-2个元素进行堆调整，...依次进行操作，直到剩余0个元素位置
第一次调整：
1，找到第一个非叶子节点，len/2-1,然后进行调整
for(int i=len/2-1;i>=0;i--){
adjust(a,i,len);
}
剩余元素调整：
2，第一次调整完毕之后，将第一个元素与最后一个元素进行交换，并将剩余的len-1个元素进行调整，并交换，一直到剩余0个元素了
for(int i=len-1;i>=0;i--){
swap(a[0],a[i]); //交换位置
adjust(a,0,i);//调整剩余的len-1个元素，其他元素的调整从0开始，因为第一次已经调整的基本是有序了，只要向下进行调整就可以了
}
调整元素：
3，调整元素，需要知道，当前元素的下标和他的孩子的下标，当前元素的下标比如是4，可以看上面的图，那么他的孩子的下标就是2*4+1和2*4+2，就是9和10，把当前元素的下标赋予max
4，判断当前元素和他的孩子元素中最大的下标，赋予max
5，如果max和当前元素的下标不同，那么需要进行交换，并进行元素调整，这里进行元素调整，是因为，你可能调整了一个，但对下面的元素有了影响，所以下面的元素也是需要进行调整的，比如下面的这种情况：当前元素比如是3
第一次，3和6进行交换：
交换完之后，导致3,4,5不是最大堆了，所以还需要进行调整，把3和5进行交换
6，很明显这是一个递归，所以需要结束条件，当max==i的时候，i就是当前元素的下标，就返回0
int adjust（int *a,int i,int len）{//i是当前元素的下标，len是当前数组的长度
int left=2*i+1;
int right=2*i+2;
int max=i;
if(left<len&&a[left]>a[max]){
max=left;
}
if(right<len&&a[right]>a[max]){
max=right;
}
if(max!=i){
swap(a[i],a[max]);
adjust(a,max,len);
}else{
return 0;
}
}
代码：（递归）
#include <iostream>
using namespace std;
int adjust_dui(int *a,int i,int len){
int left=2*i+1;//左节点的下标
int right=2*i+2;//右节点的下标
int max=i;
if(left<len&&a[left]>a[max]){
max=left;
}
if(right<len&&a[right]>a[max]){
max=right;
}
if(max!=i){
//交换
int temp=a[i];
a[i]=a[max];
a[max]=temp;
//调堆，为什么还要调堆，可能你这里调对了，但是交换完之后，下面的可能就比这个大，所以需要继续将下面的也调堆
adjust_dui(a,max,len);
}else{
return 0;
}
}
void sort_dui(int *a,int len){
for(int i=len/2-1;i>=0;i--){ //从第一个非叶子节点开始循环，第一次调堆
// cout<<i<<" ";
adjust_dui(a,i,len);
}
for(int i=len-1;i>=0;i--){
//交换，第一个和最后一个元素
int temp=a[i];
a[i]=a[0];
a[0]=temp;
//cout<<a[i]<<" ";
//把下一个剩余节点进行调堆
adjust_dui(a,0,i);
}
}
int main()
{
//1,先建堆，调堆，需要知道第一个非叶子节点（len/2-1)
//2,交换a[0]和a[len-1]
//3,继续调堆
int n;
while(cin>>n){
int *a=new int[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort_dui(a,n);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
}
return 0;
}
结果：
代码:非递归
#include <iostream>
using namespace std;
void fei_adjust(int *a,int i,int len){
int left=2*i+1;
int right=2*i+2;
int max=i;
while(1){
if(left<len&&a[left]>a[max]){
max=left;
}
if(right<len&&a[right]>a[max]){
max=right;
}
if(max!=i){//如果max和i不相等了，说明最大的已经变了，交换最大的和i位置的值
int temp=a[max];
a[max]=a[i];
a[i]=temp;
}else{//如果相等，就退出循环
break;
}
//能继续往下执行，说明最大值已经变了，那么，需要继续判断此刻max作为父亲和下面的两个孩子进行比较大小了
left=2*max+1;
right=2*max+2;
i=max;
}
}
void fei_dui(int *a,int len){
for(int i=len/2-1;i>=0;i--){
fei_adjust(a,i,len);
}
for(int i=len-1;i>=0;i--){
int temp=a[0];
a[0]=a[i];
a[i]=temp;
fei_adjust(a,0,i);
}
}
int main()
{
int a[10]={1,3,2,3,2,3,4,6,54,3};
//堆排序
fei_dui(a,10);
for(int i=0;i<10;i++){
cout<<a[i]<<" ";
}
return 0;
}
结果：
