堆-优先队列
KonnyWen 人气:1
# 堆-优先队列
前置知识：二叉树。
**参考资料**
>暂无
---
堆就是优先队列，可以用来解决动态区间查询最值问题。
堆就是一个完全二叉树，可以插入节点，删除根节点（也可以删除特定节点）。
为了方便，普通的堆节点 $i$ 的父亲就是 $[i\div2]$ （$[x]$ 表示不超过 $x$ 的最大整数）。
节点 $i$ 的左儿子是 $i\times2$，右儿子是 $i\times2+1$。
对于一个大顶堆：
每次插入节点的时候，就把节点插在完全二叉树的最后，如果它比它的父亲节点大，就把它和父亲交换，然后一直和父亲比较交换，直到父亲的值比它大，或者它已经成为树根。
每次删除根节点的时候，就把完全二叉树最后的那个节点放到根节点上，然后让最后那个节点原来的位置消失。然后把单前的根节点，跟它的左儿子比较，如果比左儿子小，就跟左儿子交换，然后不停跟左儿子比较交换知道它比左儿子大或着他没有左儿子。
时间复杂度 $O(n\log n)$。
如果你掌握了这些，那蒟蒻就放代码了：
```cpp
#include
加载全部内容