二叉堆

luckydrawbox · 2021-08-30 00:46:33 · 个人记录

预处理

使用前，请根据需要更改堆类型和比较函数 \text{cmp}。

#define H_T int
bool cmp(H_T x,H_T y){
    return x>y;
}

以上实现了一个 \text{int} 类型的大根堆。

操作

#define H_T int
struct Heap{
    int n;
    H_T heap[N];
    bool cmp(H_T x,H_T y){
        return x>y;
    }
    void up(int p){
        while(p>1)
            if(cmp(heap[p],heap[p/2])){
                swap(heap[p],heap[p/2]);
                p/=2;
            }
            else
                break;
    }
    void down(int p){
        int s=p<<1;
        while(s<=n){
            if(s<n&&cmp(heap[s+1],heap[s]))
                s++;
            if(cmp(heap[s],heap[p])){
                swap(heap[s],heap[p]);
                p=s,s=p<<1;
            }
            else
                break;
        }
    }
    void insert(H_T val){
        heap[++n]=val;
        up(n);
    }
    int gettop(){
        return heap[1];
    }
    void extract(){
        heap[1]=heap[n--];
        down(1);
    }
    void remove(int k){
        heap[k]=heap[n--];
        up(k),down(k);
    }
};

空间复杂度为 O(n)，其中 n 为元素个数，\text{gettop}() 操作的时间复杂度为 O(1)，其余操作时间复杂度为 O(\log n)。