左偏树(可并堆)

左偏树(可并堆)

定义

在这之前，我们先来阐述一些定义：

• 外节点：\(ls\) 或 \(rs\) 为空的节点
  
• 距离：节点的距离 \(dist_x\) 定义为节点 \(x\) 到距 \(x\) 最近的外节点的距离，空节点的距离为 \(-1\)
  

其次是左偏树的性质：
<ol>左偏性：即满足 \(dist_{ls}>=dist_{rs}\)
堆性质：若满足小根堆，则满足 \(v_xop>>x;        if(op==1){            cin>>y;            if(tf[x]||tf[y]) continue;            x=find(x);y=find(y);            if(x!=y) rt[x]=rt[y]=merge(x,y);                         //若不在一棵树上        }        else{            if(tf[x]){                cout