C语言算法速查手册

大根堆: a[i]>=a[i*2+1] && a[i]>=a[2*i+2], 注意不要求 左右子树 的大小关系

// 假设 i 节点之后的元素都排好序, 将 i 节点插入到堆中void sift(int* a, int n, int i){    int j,t;    t=a[i]; j = 2*i+1;    while(j<n) {        if(j<n-1 && a[j]<a[j+1]) j++; // 左右子节点中较大的节点        if(t<a[j]){            a[i]=a[j]; i=j; j = 2*i+1; // 比子节点小, 下移一层        }else break;    }    a[i] = t;}void heapSort(int* a,int n){    int i,t;    // 构建初始堆, 最大需要排序的节点为 2*i+1 <= n-1    for(i=(n>>1)-1;i>=0;i--) sift(a,n,i);    for(i=1;i<n;i++){        t=a[0]; a[0] = a[n-i]; a[n-i] = t; // 将最大的元素移动到末尾, 继续维护剩下的堆        sift(a,n-i,0);    }