// 左偏树(可并堆)模板 struct LeftistTree { struct Node { int value; // 节点值 int left; // 左子节点 int right; // 右子节点 int dist; // 距离(npl,空节点为0,叶节点为1) }; vector 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; } };