/*堆排序数组实现*/
#include <stdio.h>
#include <stdlib.h>
#define N 8
#define M N+1
/*队列*/ 
int rear=N,front=(N+1)/2;//此处有N+1个已入队 
void change(int *a,int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
/*调整*/
void deal(int data[],int n)
{
    int tag=1,parent;
    for(;tag;){
        tag=0;
        for(parent=front;parent;parent--)
        {
            if((parent*2+1<=rear)&&data[parent*2+1]>data[parent]){
                change(&data[parent*2+1],&data[parent]);
                tag=1;
            }
            if(data[parent*2]>data[parent]){
                change(&data[parent*2],&data[parent]);
                tag=1;
            }
        }//交换 
    }//判断是否没有交换 
}
/*堆排序*/ 
void Sort(int data[],int n){
    int *a=(int *)malloc((n+1)*sizeof(int));
    int i,t;//中间变量 
    for(i=1;i<n+1;i++){
        a[i]=data[i-1];
    }//end for
    /*左子女为2n,右子女为2n+1*/
    while(rear-1){
        deal(a,rear);//调整 
        /*交换头与最后一个叶子*/ 
        change(&a[rear],&a[1]);
        rear--;//砍叶子
        front=rear/2; 
    }//while 排序过程
    for(i=0;i<n;i++){
        data[i]=a[i+1];
    }   
}
void prin(int data[],int n){
    int i;
    for(i=0;i<n;i++){
        printf("%5d",data[i]);
    }//end for
    putchar('\n');
} 
int main(void)
{
    int data[N]={1,3,5,7,2,4,6,8};
    Sort(data,N);
    prin(data,N);
    return 0;
}