关于程序员:PAT堆模板

// 留神为不便操作，堆的下标从 1 开始
const int maxn = 100;
int heap[maxn], n = 10;

// 向下调整
void downAdjust(int low, int high){
    int i = low, j = 2*i;
    while(j <= high){if(j + 1 <= high && heap[j+1] > heap[j]){// 此处不要遗记判断 j + 1 是否超过了 high
            j = j+1;
        }
        if(heap[i] < heap[j]){swap(heap[i], heap[j]);
            i = j;
            j = 2*i;
        }else{break;}
    }
}

// 建堆
void createHeap(){for(int i = n/2; i >= 1; i--){downAdjust(i, n);
    }
}

// 删除堆顶元素
void delTop(){heap[1] = heap[n--];
    downAdjust(1, n);   // 此处前面的是 n，因为 n 曾经自减了
}

// 向上调整
void upAdjust(int low, int high){
    int i = high, j = i/2;
    while(j >= low){if(heap[i] > heap[j]){swap(heap[i], heap[j]);
            i = j;
            j = i/2;
        }else{break;}
    }
}

// 增加元素
void insert(int x){heap[++n] = x;
    upAdjust(1, n);
}

// 堆排序
void heapSort(){createHeap();
    for(int i = n; i > 1; i--){// 从后往前倒着枚举替换
        swap(heap[1], heap[i]);
        downAdjust(1, i-1);
    }
}