堆
堆（一般指二叉堆），实质就是一颗完全二叉树，用来维护单调性
堆可以实现插入新值，得到最值（直接取堆顶值），删除最值。
插入新值，从堆尾插入，不断比较 上浮；删除最值，就是将堆顶替换掉，可以用堆尾 替换，并不断比较 下沉，用树的深度的时间花销维护堆的单调性
感受一下维护堆的过程，可以用数组实现（一一对应），手写堆就很容易写
手写堆 code
inline void up(int u)
{
if (u / 2 && a[u / 2] > a[u])
swap(a[u], a[u / 2]), up(u / 2);
}
inline void down(int u)
{
int v = u;
if (u * 2 <= cnt && a[u * 2] < a[u])
v = u * 2;
if (u * 2 + 1 <= cnt && a[u * 2 + 1] < a[v])
v = u * 2 + 1;
if (v != u)
swap(a[u], a[v]), down(v);
}
inline void push(int x)
{
a[++ cnt] = x;
up(cnt);
}
inline void pop()
{
a[1] = a[cnt];
cnt --;
down(1);
}
priority_queue 就是 STL 里的堆（默认大根堆）
另外，由于这个用堆尾替换堆顶的等价操作（等价于删除堆顶操作），两个相等的元素可能位置会有变化，即后进堆的可能深度更浅一些，所以，堆排序是不稳定的
标签：int,东西,void,新值,七七八八,插入,inline,数据结构,最值 From： https://www.cnblogs.com/wenzieee/p/18417646