堆的基本操作

down和up操作

//这里以小根堆为例,将根结点与孩子结点中的最小结点交换
void down(int u){
    int t=u;
    if(u*2<=sz&&h[u*2]<h[t]) t=u*2;
    if(u*2+1<=sz&&h[u*2+1]<h[t]) t=u*2+1;
    if(t!=u){
        swap(h[u],h[t]);
        down(t);
    }
}

//up操作用于在已经建立好的堆的尾部插入数据时维护堆的有效性
void up(int u){
    while(u/2>0&&h[u/2]>h[u]){
        swap(h[u],h[u/2]);
        u=u/2;
    }
}

堆的建立

//方法1： 插入法建立堆 O(nlogn)
void insert(int x){
    h[++sz]=x;
    up(sz);
}
for(int i=1;i<=n;++i) cin>>x && insert(x);

//方法2：通过调整建立堆 O(n)
for(int i=sz/2;i;--i) down(i);

删除堆中的元素

// 删除堆中k号元素
void delk(int k){
    h[k]=h[sz--];
    down(k),up(k); //down和up 最多执行一个
}

修改堆中的元素

// 修改堆中k号元素
void delk(int k，int x){
    h[k]=x;
    down(k),up(k); //down和up 最多执行一个
}