(Treap = Tree + Heap)
树堆（Treap），在数据结构中也称Treap，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。
----百度百科
要了解Treap，就先要看看什么是二叉搜索树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
----百度百科
Treap既有BST的性质，也有堆的性质，Treap的每个结点额外附加一个随机值（优先级），让他们按照关键码构成BST的同时也满足堆的性质（父节点优先级高于或低于子节点优先级），因为优先级是随机的，这样在绝大多数情况下我们得到的树都是平衡的，不容易被卡成链， 单次操作期望时间复杂度为O(logn)。
操作：
1.定义
struct Treap {
int dat, val;
int cnt, size, l, r;
} e[N];
dat 随机优先级； val BST关键码； cnt 当前结点数量； size 子树结点数量； l，r 左右儿子。
2.更新
void update(int p) {
e[p].size = e[e[p].l].size + e[e[p].r].size + e[p].cnt;
}
更新结点size值。
3.新建结点
int newpoint(int val) {
e[++tot].val = val;
e[tot].dat = rand();
e[tot].cnt = e[tot].size = 1;
return tot;
}
4.建树
void build() {
newpoint(-inf); newpoint(inf);
root = 1; e[root].r = 2; update(root);
}
初始化两个结点，设置为无限大和无限小。
5.左右旋转
左右旋转是在保证BST性质前提下（中序遍历不变）将一个结点向上或者向下转，实质上是父节点变成了子节点，子节点变成了父节点。
左旋和右旋分别对应着将左儿子翻上来和将右儿子翻上来。
具体操作
void zig(int &p) {//左旋
int q = e[p].l;
e[p].l = e[q].r; e[q].r = p; p = q;
update(e[p].r); update(p);
}
void zag(int &p) {//右旋
int q = e[p].r;
e[p].r = e[q].l; e[q].l = p; p = q;
update(e[p].l); update(p);
}
//p引用的是旋转前的根结点
6.插入
插入一个值为val的结点，若存在关键码为val的结点，将此结点数量 + 1，若不存在，根据val大小和当前结点val大小向左右两边找，最后新建结点，返回时要维护堆性质。
void insert(int &p, int val) {
if(p == 0) {
p = newpoint(val); return ;
}
if(e[p].val == val) {
e[p].cnt++; update(p);
return ;
}
if(val < e[p].val) {
insert(e[p].l, val);
if(e[p].dat < e[e[p].l].dat) zig(p);
} else {
insert(e[p].r, val);
if(e[p].dat < e[e[p].r].dat) zag(p);
}
update(p);
}
7.删除结点
删除一个值为法val的结点，先在树中查找值为val的结点：
1.若结点cnt(数量) 大于1，则可以直接减1，返回；
2.若结点数量为1，将其向下旋转，转到叶结点时直接删除；
注意：在向下旋转时应维护堆的性质，若是大根堆，选取子节点中dat大的结点与其交换。
void delet(int &p, int val) {
if(p == 0) return ;
if(val == e[p].val) {
if(e[p].cnt > 1) {
e[p].cnt--; update(p); return ;
} else {
if(e[p].l || e[p].r) {//不为叶结点
if(e[e[p].l].dat > e[e[p].r].dat || !e[p].r)
zig(p), delet(e[p].r, val);
else
zag(p), delet(e[p].l, val);
update(p);
} else p = 0;
}//else
return ;
}
if(val < e[p].val) delet(e[p].l, val);
else delet(e[p].r, val);
update(p);
}
8.排名
包括根据值查排名和根据排名查值。
1.根据值查排名(rankk();)我们只需要从根节点往下找，如果当前结点值较大，递归查询左儿子；如果当前结点值较小，递归查询右儿子，返回时要加上左子树结点数和当前节点的数量。
2.根据排名查值(arcrank();），同样，如果当前结点值较大， 递归查询左儿子； 如果当前结点值较小，递归查询右儿子，注意查询右儿子时应将排名减去左子树和当前结点的数量。
int rankk(int p, int val) {
if(p == 0) return 0;
if(val == e[p].val) return e[e[p].l].size + 1;
if(val < e[p].val) return rankk(e[p].l, val);
return rankk(e[p].r, val) + e[e[p].l].size + e[p].cnt;
}
int arcrank(int p, int k) {
if(p == 0) return inf;
if(k <= e[e[p].l].size) return arcrank(e[p].l, k);
if(k <= e[p].cnt + e[e[p].l].size) return e[p].val;
return arcrank(e[p].r, k - e[p].cnt - e[e[p].l].size);
}
9.查询前驱和后继
拿前驱来说，若查询v的前驱，分两种情况：
1.找到了值为v的结点，那么v的前驱就是v的左子树中值最大的点的值， 找到直接返回。
2.没有找到结点为v的值，需要不断比较，若当前结点值比v小且比找到的答案大，就更新答案。
后继与前驱类似。
int getper(int val) {
int p = root, ans = 1;//初始化为无限小
while(p) {
if(val == e[p].val) {
if(e[p].l) {
p = e[p].l;
while(e[p].r) p = e[p].r;
ans = p;
}
break;
}
if(e[p].val < val && e[ans].val < e[p].val) ans = p;//比较，更新答案
if(val < e[p].val) p = e[p].l;
else p = e[p].r;
}
return e[ans].val;
}
int getnext(int val) {
int p = root, ans = 2;//初始化为无限大
while(p) {
if(val == e[p].val) {
if(e[p].r) {
p = e[p].r;
while(e[p].l) p = e[p].l;
ans = p;
}
break;
}
if(e[p].val > val && e[ans].val > e[p].val) ans = p;
if(val < e[p].val) p = e[p].l;
else p = e[p].r;
}
return e[ans].val;
}
完整代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100005;
const int inf = (1 << 31) - 1;
int n, root, tot = 0;
struct Treap {
int dat, val;
int cnt, size, l, r;
} e[N];
void update(int p) {
e[p].size = e[e[p].l].size + e[e[p].r].size + e[p].cnt;
}
int newpoint(int val) {
e[++tot].val = val;
e[tot].dat = rand();
e[tot].cnt = e[tot].size = 1;
return tot;
}
void build() {
newpoint(-inf); newpoint(inf);
root = 1; e[root].r = 2; update(root);
}
void zig(int &p) {
int q = e[p].l;
e[p].l = e[q].r; e[q].r = p; p = q;
update(e[p].r); update(p);
}
void zag(int &p) {
int q = e[p].r;
e[p].r = e[q].l; e[q].l = p; p = q;
update(e[p].l); update(p);
}
void insert(int &p, int val) {
if(p == 0) {
p = newpoint(val); return ;
}
if(e[p].val == val) {
e[p].cnt++; update(p);
return ;
}
if(val < e[p].val) {
insert(e[p].l, val);
if(e[p].dat < e[e[p].l].dat) zig(p);
} else {
insert(e[p].r, val);
if(e[p].dat < e[e[p].r].dat) zag(p);
}
update(p);
}
void delet(int &p, int val) {
if(p == 0) return ;
if(val == e[p].val) {
if(e[p].cnt > 1) {
e[p].cnt--; update(p); return ;
} else {
if(e[p].l || e[p].r) {
if(e[e[p].l].dat > e[e[p].r].dat || !e[p].r)
zig(p), delet(e[p].r, val);
else
zag(p), delet(e[p].l, val);
update(p);
} else p = 0;
}
return ;
}
if(val < e[p].val) delet(e[p].l, val);
else delet(e[p].r, val);
update(p);
}
int rankk(int p, int val) {
if(p == 0) return 0;
if(val == e[p].val) return e[e[p].l].size + 1;
if(val < e[p].val) return rankk(e[p].l, val);
return rankk(e[p].r, val) + e[e[p].l].size + e[p].cnt;
}
int arcrank(int p, int k) {
if(p == 0) return inf;
if(k <= e[e[p].l].size) return arcrank(e[p].l, k);
else if(k <= e[p].cnt + e[e[p].l].size) return e[p].val;
return arcrank(e[p].r, k - e[p].cnt - e[e[p].l].size);
}
int getper(int val) {
int p = root, ans = 1;
while(p) {
if(val == e[p].val) {
if(e[p].l) {
p = e[p].l;
while(e[p].r) p = e[p].r;
ans = p;
}
break;
}
if(e[p].val < val && e[ans].val < e[p].val) ans = p;
if(val < e[p].val) p = e[p].l;
else p = e[p].r;
}
return e[ans].val;
}
int getnext(int val) {
int p = root, ans = 2;
while(p) {
if(val == e[p].val) {
if(e[p].r) {
p = e[p].r;
while(e[p].l) p = e[p].l;
ans = p;
}
break;
}
if(e[p].val > val && e[ans].val > e[p].val) ans = p;
if(val < e[p].val) p = e[p].l;
else p = e[p].r;
}
return e[ans].val;
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d", &n); build();
while(n--) {
int opt, x; scanf("%d%d", &opt, &x);
switch(opt) {
case 1:
insert(root, x);
break;
case 2:
delet(root, x);
break;
case 3:
printf("%d
", rankk(root, x) - 1);
break;
case 4:
printf("%d
", arcrank(root, x + 1));
break;
case 5:
printf("%d
", getper(x));
break;
case 6:
printf("%d
", getnext(x));
break;
}
}
return 0;
}