ToB企服应用市场:ToB评测及商务社交产业平台

标题: 左偏树(可并堆) [打印本页]

作者: 络腮胡菲菲 时间: 2024-8-8 13:10
标题: 左偏树(可并堆)
左偏树(可并堆)

定义

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

外节点：\(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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)