#include <stdio.h>
#include <stdlib.h>
//建堆，调整堆，堆排序
void swap(int arr[],int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
//heapify函数实现的是，把最大的节点调整到父节点上
void heapify(int tree[],int n,int i){
if(i>=n)
return;
int c1=2*i+1;
int c2=2*i+2;
int max=i;
if(c1<n&&tree[max]<tree[c1]){
max=c1;
}
if(c2<n&&tree[max]<tree[c2]){
max=c2;
}
if(max!=i){
swap(tree,max,i);
heapify(tree,n,max);
}
}
//接下来要做的是，建堆，也就是从最后一个非叶子节点，去调整
void build_heap(int tree[],int n){
int last_node=n-1;
int parent=(last_node-1)/2;
int i;
for(i=parent;i>=0;i--){
heapify(tree,n,i);
}
}
//然后，进行堆排序，拿出根节点与最后一个交换，然后调整堆，继续
void heapSort(int tree[],int n){
build_heap(tree,n);
int i;
for(i=n-1;i>=0;i--){
swap(tree,i,0);
heapify(tree,i,0);
}
}
int main()
{
int tree[]={2,5,3,1,10,4};
int n=6;
heapSort(tree,n);
int i;
for(i=0;i<n;i++){
printf("%d\n",tree[i]);
}
return 0;
}
