二叉堆：
插入后是完全二叉树
插入：
在最下一层最右边的叶子结点之后插入。
如果一层已满，就新增一层。
如果这个节点的值大于父亲的权值，就交换，重复直到不满足或不定根
删除：
直接删掉最后一个节点处的根节点。在该节点的儿子中找一个最大的，与该节点交换，直到底层
二叉堆代码：
struct pq
{
int heap[MAX];
int tot=0;
void push(int k)
{
heap[++tot]=k;
int u=tot;
while(u)
{
int fa=u>>1;
if(heap[fa]<heap[u])swap(heap[fa],heap[u]);
else break;
}
u=fa;
}
void pop()
{
swap(heap[tot],heap[1]);
tot--;
push_down(1);
}
void push_down(int u)
{
while(ls(u)<=tot)
{
if(heap[u]<max(heap[ls(u)],heap[rs(u)]))
{
if(rs[u]<=tot&&heap[rs(u)]>heap[ls(u)])
{
swap(heap[u],heap[rs(u)]);
u=rs(u);
}
else
{
swap(heap[u],heap[ls(u)]);
u=ls(u);
}
}
}
}
void build(int n)
{
for(int i=n>>1;i>=1;i--)
{
push_down(i);
}
}
};
（一般直接用priority_queue）
并查集：
（以前记过一部分了）
启发式合并:选深度小的数并到大的树中，并记录新的深度
删除：把叶子节点父亲设为自己
STL:
sort():
内定按<排序，可以自己定义<改变顺序，也可以写cmp函数
pair:
pair<int,string> p=(…,…);
p=make_pair(…,…);
vector:
v.capacity()//能容纳的元素个数,>size()
v.resize()//将size设为…
v.reserve()//将capacity改为…
vector::iterator it;//auto it=数据类型
*it取出其指向的值
for(vector<int>::iterator it=v.begin();it!=v.end();it++)
{
...
}//指针遍历
queue:
没有clear()
有empty()
priority_queue:
从小到大排序：priority_queue<int,vector,greater > …;
可以通过重载运算符排序结构体等
map:
映射
map<…,…> mp;
for(map<int,string>::iterator p=mp.begin();p!=mp.end();++p)
{
cout<<p->first<<' '<<p->second<<endl;
}//正序遍历
for(map<int,string>::reverse iterator p=mp.rbegin();p!=mp.rend();++p)
{
cout<<p->first<<' '<<p->second<<endl;
}//倒序遍历
unordered_map:
无序存储
时间复杂度O(1),空间复杂度O(n),常数巨大
会去重
set:
自带lowerbound()和upperbound(),返回迭代器
对于自定义结构体，要重载小于号
会去重
multiset:
支持可重集合
erase会将相同的元素全部删掉
成员函数count()可以统计一个值出现了多少次
unordered_set:
无排序的set
基本不用
红黑树：
#include<ext/pb_ds/treepolicy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T;
//tree<数据类型，无类型（不变），排序规则，树的类型，树顺序动态更新？？？（不变）> 树的名字;
//下列是可用函数
T.insert();
T.erase();
T.order_of_key();
T.find_by_order(k);
T.lower_bound();
T.upper_bound();