二叉堆

模板（大根堆）

void up(int x){
    while(x>1 && tr[x]>tr[x/2]){
        swap(tr[x],tr[x/2]);
        x/=2;
    }
}
void down(int x,int n){
    int t;
    while(2*x<=n){
        t=2*x;
        if(t+1<=n&&tr[t]<tr[t+1]) t++;
        if(tr[x]>=tr[t]) break;
        swap(tr[x],tr[t]);
        x=t;
    }
}

原理

• 插入
  在最下一层最右边的叶子之后插入，如果最下一层已满，就新增一层（数组实现下插在尾部）。如果节点权值大于父节点，就交换，一直到不满足或到根节点为止。
• 删除
  将最下一层最右边的叶子节点与根节点交换，如果根节点小于任一子节点，将节点与最小的子节点交换（很重要），一直到不满足或越界为止。
• 增减权值 向上/向下移动节点
• 建堆
  参照插入
  时间复杂度: \log 1+\log 2+\log 3...+\log n=\Theta(n \\log n)
  更好的方式? 向下调整（我自己还没搞清楚qaq）

    for(int i=n;i>=1;i--) down(i);

扩展

1. 对顶堆
   对顶堆由一个大根堆与一个小根堆组成，小根堆维护大值即前 k 大的值（包含第 k 个），大根堆维护小值即比第 k 大数小的其他数。

踩过的坑

1. 向下时将节点与最小的子节点交换（大根堆）
2. 弹出时一定记得要检查有没有元素
3. 容易把边界变量弄混（呜呜呜