#include<stdio.h>
void swap(int *a,int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}
void shiftDown(int a[],int i,int n){
	int temp=a[i];
	while(2*i+1<n){
		int child=2*i+1;
		if(child<n-1&&a[child]<a[child+1]){
			child++;
		}
		if(temp<a[child]){
			a[i]=a[child];
		}else{
			break;
		}
		i=child;
	}
	a[i]=temp;
}
void heapSort(int a[],int n){
	for(int i=(n-2)/2;i>=0;i--){
		shiftDown(a,i,n);
	}
	for(int i=n-1;i>0;i--){
		swap(&a[0],&a[i]);
		shiftDown(a,0,i);
	}
}
int main(){
	int n=7;
	int a[7]={9,8,7,6,5,4,3};
	printf("\n\n原数组:");
	for(int i=0;i<n;i++){
		printf("  %d",a[i]);
	}
	printf("\n经过堆排序后的数组:");
	heapSort(a,n);
	for(int i=0;i<n;i++){
		printf("  %d",a[i]);
	}
	return 0;
}