预备知识：二叉查找树、堆（heap）、平衡二叉树（AVL）的基本操作（左旋右旋）
定义：
Treap。平衡二叉树。Tree+Heap。树堆。
- 每个结点两个键值（key、priority）。
- 性质1. Treap是关于key的二叉排序树。
- 性质2. Treap是关于priority的堆。（非二叉堆，因为不是完全二叉树）
- 结论1. key和priority确定时，treap唯一。
- 作用1. 随机分配的优先级，使数据插入后更不容易退化为链。就像是将其打乱再插入。所以用于平衡二叉树。
基本操作
要满足它的两个性质，先让它满足二叉排序树的性质，再通过左旋或右旋，来满足堆的性质。
左旋：
下面代码仅为理解用，板子的话就不一样啦：
void Zag(Treap &T){
Treap Q=T->right;
T->right=Q->left;
Q->left=T;
T=Q;
}
右旋：
void Zig(Treap &T){
Treap Q=T->left;
T->left=Q->right;
Q->right=T;
T=Q;
}
插入
- 分配一个优先级（用一个随机函数）
- 和二叉查找树一样把新结点当叶子插入
- 插入后，若破坏堆性质，就把优先级高的旋转上来
复杂度：最多操作次数为树的高度，即O（h），高度期望值=O（logn），故复杂度为O（logn）
删除
优先级有定义（就是key对应的priority不改变）：
把要删除的旋转（把俩孩子里优先级高的旋转上来），直到只有一个孩子或者无孩子，直接删去，孩子直接代替自己。
复杂度：旋转1次是O（1），最多h次旋转，故为O（logn）
优先级随机设定：
和普通二叉树删除操作一样，把直接后继或前继结点交换上来，然后删去后续结点。
复杂度：查找直接后继最多O（h），故也是O（logn）
模板
#include <cstdio>
#include <cstdlib>
#define N 100005
using namespace std;
int cnt=1,rt=0; //节点编号从1开始
struct Treap{
int key, pri, size, son[2]; //保证父亲的pri大于儿子的pri
}T[N];
void rotate(int p, int &x){
int y=T[x].son[!p];
T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size;
T[x].son[!p]=T[y].son[p];
T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size;
T[y].son[p]=x;
x=y;
}
//插入，调用ins(key,rt)
void ins(int key, int &x){
if(x == 0)
T[x = cnt++]=(Treap){key,rand(),1};
else{
T[x].size++;
int p=key < T[x].key;
ins(key, T[x].son[!p]);
if(T[x].pri < T[T[x].son[!p]].pri)
rotate(p, x);
}
}
//删除，调用del(key,rt)
void del(int key, int &x){
if(T[x].key == key){
if(T[x].son[0] && T[x].son[1]){
int p=T[T[x].son[0]].pri > T[T[x].son[1]].pri;
rotate(p, x);
del(key, T[x].son[p]);
}
else
x=T[x].son[0]?T[x].son[0]:T[x].son[1];
}else{
T[x].size--;
int p=T[x].key > key;
del(key, T[x].son[!p]);
}
}
//找出第p小的节点的编号，第p小的值为T[find(p,rt)].key
int find(int p, int x){
if(p == T[T[x].son[0]].size+1)
return x;
if(p > T[T[x].son[0]].size+1)
return find(p-T[T[x].son[0]].size-1, T[x].son[1]);
else
return find(p, T[x].son[0]);
}
//找出值小于等于key的节点个数
int find_NoLarger(int key, int x){
if(x == 0)
return 0;
if(T[x].key <= key)
return T[T[x].son[0]].size+1+find_NoLarger(key, T[x].son[1]);
else
return find_NoLarger(key, T[x].son[0]);
}
int main(){
srand(19970502);
return 0;
}