// 左偏树(可并堆)模板
struct LeftistTree {
struct Node {
int value; // 节点值
int left; // 左子节点
int right; // 右子节点
int dist; // 距离(npl,空节点为0,叶节点为1)
};
vector<Node> heap; // 堆节点数组,0号节点为空节点
// 构造函数,初始化空节点
LeftistTree(int reserveSize = 0) {
heap.reserve(reserveSize + 1);
heap.push_back({0, 0, 0, 0}); // 0号节点作为空节点
}
// 创建新节点
int newNode(int value) {
heap.push_back({value, 0, 0, 1});
return (int)heap.size() - 1;
}
// 比较优先级,返回a是否优先于b
// 可根据需要重写(此处为示例:值大的优先)
bool higherPriority(int a, int b) {
if (b == 0) return true; // b为空
if (a == 0) return false; // a为空
return heap[a].value > heap[b].value; // 大根堆
}
// 合并两个堆,返回合并后的根节点
int merge(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
// 确保a的优先级更高
if (!higherPriority(a, b)) swap(a, b);
// 递归合并右子树
heap[a].right = merge(heap[a].right, b);
// 维护左偏性质:左子树dist >= 右子树dist
if (heap[heap[a].left].dist < heap[heap[a].right].dist) {
swap(heap[a].left, heap[a].right);
}
// 更新dist
heap[a].dist = heap[heap[a].right].dist + 1;
return a;
}
// 弹出堆顶(删除根节点)
int pop(int root) {
return merge(heap[root].left, heap[root].right);
}
// 获取堆顶值
int top(int root) {
return heap[root].value;
}
// 判断堆是否为空
bool empty(int root) {
return root == 0;
}
};typedef pair<int,int> P; // 存储键值对,通常用于比较优先级
struct Node {
int l, r, d; // l:左孩子, r:右孩子, d:距离(null路径长度)
P v; // 存储的值(键值对)
Node(){}
Node(int _l,int _r,int _d,P _v){l=_l,r=_r,d=_d,v=_v;}
} T[N]; // 数组存储所有节点
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(T[a].v < T[b].v)swap(a,b);
T[a].r = merge(T[a].r,b);
if(T[T[a].l].d < T[T[a].r].d)swap(T[a].l,T[a].r);
T[a].d=T[a].r ? T[T[a].r].d+1:0;
return a;
}
int pop(int a){
int l = T[a].l,r=T[a].r;
T[a].l=T[a].r=T[a].d=0;
return merge(l,r);
}