/* 堆排序的算法源程序*/

#include<stdio.h>

#define MAXNUM 100
#define TRUE 1
#define FALSE 0
typedef int KeyType;
typedef int DataType;

typedef struct {
    KeyType key;         /* 排序碼字段 */
    /*DataType info;     記錄的其它字段 */
} RecordNode;

typedef struct {
    int n;               /* n為文件中的記錄個(gè)數(shù)，n<MAXNUM */
    RecordNode record[MAXNUM];
} SortObject;

/* 定義宏是為了使程序清晰 */ 
#define leftChild(i) (2*(i)+1)

void  sift(SortObject * pvector, int i, int n) {
    int child; 
    RecordNode temp = pvector->record[i], *data = pvector->record;

    child = leftChild(i);      /* Rchild是R0的左子女 */
    while(child<n) {
        if (child < n-1 && data[child].key < data[child+1].key)
            child++;           /* child 指向Ri的左、右子女中排序碼較大的結(jié)點(diǎn) */
        if (temp.key < data[child].key) {
            data[i] = data[child]; 
            i = child;  child = leftChild(i);/* child換到父結(jié)點(diǎn)位置，繼續(xù)調(diào)整*/
        }
        else break;            /* 調(diào)整結(jié)束 */
    }
    data[i] = temp;            /* 將記錄Ri放入正確位置 */
}

void  heapSort(SortObject * pvector) {    /* 對(duì)記錄R0到Rn-1進(jìn)行堆排序 */
    int i, n = pvector->n;
    RecordNode temp, *data = pvector->record;
    
    for (i = n/2-1; i >= 0; i--)
        sift(pvector, i, n);              /* 建立初始堆 */
    for (i = n-1; i > 0; i--) {           /* 進(jìn)行n-1趟堆排序 */
        temp = data[0];                   /* 當(dāng)前堆頂記錄和最后一個(gè)記錄互換 */
        data[0] = data[i];
        data[i] = temp;
        sift(pvector, 0, i);              /* 從R0到Ri-1重建堆 */
    }
}

SortObject vector={8, 49,38,65,97,76,13,27,49};

int main(){
    int i;
    heapSort(&vector);
    for(i = 0; i < 8; i++)
        printf("%d ", vector.record[i]);
    getchar(); 
    return 0;
}