左偏树
啥是左偏树呢？
大概是这样的
这里需要注意两点：
- 左偏树是一棵二叉树，也是一种可并堆，拥有堆的性质，可以像堆一样合并。
- 左偏树顾名思义，有“左偏”的特点，既每个左子树节点的dist一定大于等于右子树节点的dist。
就比如像是什么\(priority \_ queue\)啥的既支持插入一个元素，还能查询最小/大元素，这直接STL就可以操作。但是要是某些毒瘤题目里让我们来使两个堆合并（其实算是正常操作吧），就不能用STL的\(priority\_queue\)来肝了【前提是不算\(pb\_ds\)那种神仙专属库】
有关左偏树的某些定义
距离
我们不妨设（能且仅能设）\(dist[i]\)表示一个节点它到离它最近的外节点的距离。
叶子节点的dist=0，空节点的dist=0
外节点
我们定义一个节点为外节点，当且仅当这个节点的左子树和右子树中的一个是空节点。（注意外节点不是叶子节点）
一些神奇的操作
合并
因为左偏树节点不满足完全二叉树而且十分左偏的性质，我们可以在一个log的复杂度中合并两个堆。
这个合并分为下面几步：
- 1：若是其中一个堆是空的，直接return 另一个堆
2：否则选择一个堆顶val较大的堆作为父亲节点
3：(如果是val相等那么使用堆顶dist相对比较大的堆作为父亲节点) - 那么现在我们将根节点的右子树和另一个堆递归合并即可
- 如果左右儿子dist需要修正那么交换左右儿子
- 更新根节点dist
插入一个新的元素
一个新的元素就是一个只有一个节点的左偏树，直接合并这个左偏树和原先的左偏树即可。
弹出栈顶元素
我们可以合并根节点的左右子树，然后删除根节点
\(Code\)
#include <iostream>
#include <cstdio>
using namespace std;
inline int read() {
int num = 0;
char ch = getchar();
bool flag = false;
while (!isdigit(ch)) flag = ch == '-', ch = getchar();
while (isdigit(ch)) num = (num << 1) + (num << 3) + (ch ^ 48), ch = getchar();
return flag ? -num : num;
}
template<typename Tp>
struct Heap_node {
int lson, rson;
int dist;
Tp val;
Heap_node() {
lson = rson = dist = 0;
}
};
const int SIZE = 1000086;
struct Heap {
Heap_node<int> tree[SIZE];
int rt, cnt, tot;
inline int New(int val) {
++tot;
tree[tot].val = val;
return tot;
}
inline void set_dist(int n) {
tree[n].dist = tree[n].rson ? (tree[tree[n].rson].dist + 1): 0;
}
int merge(int a, int b) {
if (a == 0 || b == 0)
return a + b;
else if (tree[a].val > tree[b].val)
swap(a, b);
else if (tree[a].dist < tree[b].dist)
swap(a, b);
tree[a].rson = merge(tree[a].rson, b);
if (tree[a].lson != 0 && tree[a].rson != 0) {
if (tree[tree[a].lson].dist < tree[tree[a].rson].dist)
swap(tree[a].lson, tree[a].rson);
} else if (tree[a].lson == 0 && tree[a].rson != 0)
swap(tree[a].lson, tree[a].rson);
set_dist(a);
return a;
}
inline void insert(int val) {
cnt++;
int b = New(val);
rt = merge(rt, b);
}
inline void pop() {
if (rt == 0)
return;
else {
cnt--;
int a = tree[rt].lson, b = tree[rt].rson;
rt = merge(a, b);
}
}
inline int top() {
return rt ? tree[rt].val : 0;
}
inline size_t size() {
return cnt;
}
Heap() {
rt = tot = cnt = 0;
}
} h;
int n = read();
int main() {
while (n--) {
int opt = read();
switch (opt) {
case 1:
h.insert(read());
break;
case 2:
printf("%d\n", h.top());
break;
case 3:
h.pop();
break;
default:
break;
}
}
return 0;
}