《算法》 堆排序

/*  Subject: Heap_sort   Date : 2012-01-30
    个人感觉 ： 建堆 -> 堆化 -> 堆排 -> 堆化 -> 堆排 -> 堆化 ......  */
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define Bug cout << "here\n";

using namespace std;
const int N = 105;

int a[N];

void Heapify(int a[], int i, int size) { /* 大根堆化 使以 i 为根的子树成为最大堆 */
    int ls = 2*i, rs = 2*i+1;
    int large;
    if(ls <= size && a[ls] > a[i]) {
        large = ls;
    }
    else large = i;
    if(rs <= size && a[rs] > a[large]) {
        large = rs;
    }
    if(large != i) {
        swap(a[large], a[i]);
        Heapify(a, large, size);   // 子树原为大堆化 , 父辈树调整 -> 可能影响子树 ->  所以 ： 子树重新调整(堆化)。
    }
}
void Build_Heap(int a[], int size) { // 建立堆树
    for(int i = size/2; i >= 1; i--) {
        Heapify(a, i, size);
    }
}

void Heap_sort(int a[], int size) {
     Build_Heap(a, size);
     int len = size;
     for(int i = len; i >= 2; i--) {
        swap(a[i], a[1]);
        len--;
        Heapify(a, 1, len);
     }
}
int main() {
    int n, i;
    scanf("%d", &n);
    for(i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    Heap_sort(a, n);
    for(i = 1; i <= n; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
    system("pause");
    return 0;
}

/* 测试数据
7
8 5 4 9 2 3 6
*/