登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.13 可并堆 › 可并堆 / 搜索
JSON MD

2.13 可并堆

左偏树(可并堆)模板 LeftistTree
67 行
CPP JSON
C++ 67 行 CPP
// 左偏树(可并堆)模板
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;
    }
};
左偏树-P3377 luogu-p3377
21 行
CPP JSON
C++ 21 行 CPP
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);
}
已复制