#include<stdio.h>
void swap(int& a,int& b)
{
if(a!=b)
{
a^=b;
b^=a;
a^=b;
}
}
void MAX_HEAPIFY(int a[],int length,int i)//a数组第一个存值
{
int large=i;
if(2*i<length && a[i]<a[2*i]){
large = 2*i;
}
if(2*i+1<length && a[large]<a[2*i+1]){
large = 2*i+1;
}
if(large!=i){
swap(a[i],a[large]);
MAX_HEAPIFY(a,length,large);
}
}
void BUILD_MAX_HEAP(int a[],int length)//将每个非叶子节点从下向上调用MAX_HEAPIFY
{
for(int i = length/2-1;i>=0;i--)
{
MAX_HEAPIFY(a,length,i);
}
}
void HEAP_SORT(int a[],int length)
{
BUILD_MAX_HEAP(a,length);
for(int i = length-1; i>0;i--)
{
swap(a[0],a[length-1]);
MAX_HEAPIFY(a,--length,0);//保证最大堆的性质
}
}
int main()
{
int a[10] = {16,4,10,14,7,9,3,2,8,1};
HEAP_SORT(a,10);
for(int i=0;i<10;i++)
{
PRintf("%d ",a[i]);
}
}
