堆排序的实现代码

根据《算法导论》堆排序一节的描述实现。

代码如下（已验证）

#define LEFT(a) ((a)<<1)+1
#define RIGHT(b) ((b)<<1)+2
#define swap(a,b) a ^=b;b^=a;a^=b
void output(int input[], int size){
    if(input == NULL) return;
    int i = 0;
    while(i<size){
        printf("%d ",input[i]);
        i++;
    }
    printf("\n");
}

void MaxHeapify(int input[], int tar, int size){
    if(input == NULL) return;
    int largest = tar;
    if(LEFT(tar)<size && input[LEFT(tar)]>input[tar]){
        largest = LEFT(tar);
    }
    if(RIGHT(tar)<size && input[RIGHT(tar)]>input[largest]){
        largest = RIGHT(tar);
    }
    if(tar!=largest){
        swap(input[tar], input[largest]);
        MaxHeapify(input,largest, size);
    }

}

void CreateHeap(int input[], int size){
    if(input == NULL) return;
    int root = (size-1)>>1;
    for(;root>=0;root--){
        MaxHeapify(input, root,size);
    }
}
void HeapSort(int input[], int size){
    if(input == NULL) return;
    CreateHeap(input, size);
    int end = size-1;
    for(;end>0;end--){
        swap(input[0],input[end]);
        printf("Select Max %d endIndex = %d\n", input[end],end-1);
        MaxHeapify(input,0,end);
        output(input, size);
    }
}


int main(){
    int input[] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
    int size = sizeof(input)/sizeof(int);
    HeapSort(input, size);
    output(input,size);
}