//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "左偏树（可并堆）模板": {
        "prefix": "acm-2.13LeftistTree",
        "body": [
            "// 左偏树（可并堆）模板",
            "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;",
            "    }",
            "};"
        ],
        "description": "插入 左偏树（可并堆）模板"
    }
}