skew heap

简介

就是左偏树改装一下，不再判断左子树高度比右子树高，而是每次插入就交换左右子树

与左偏树对比

code:

//leftist heap
int merge(int x,int y){
    if(!x || !y) return x+y;
    if(leq(y,x)) swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]);
    dis[x]=dis[rc[x]]+1;
    return x;   
} 

//skew heap
int merge(int x,int y){
    if(!x || !y) return x+y;
    if(leq(y,x)) swap(x,y);
    rc[x]=merge(rc[x],y);
    swap(lc[x],rc[x]);
    return x;
}

看起来很像AVL转splay的操作？那么来分析下复杂度吧

复杂度证明

势能分析

设\(\phi(i)\)表示\(i\)个节点的树中，重节点的个数

重节点为右子树大小大于左子树的节点，轻节点相反

假设合并的两个树\(a\),\(b\)右路径的重节点，轻节点个数为\(l_a,l_b,h_a,h_b\)

那么每次操作实际开销为\(c_i=l_a+l_b+h_a+h_b\)

因为每次走右路径，最多只会经过这些节点

则均摊开销\(\hat c_i=c_i+\Delta \phi(i)\)

因为每个节点都会交换左右子树，且重节点的合并发生在右子树，所以重节点一定变为轻节点(轻节点不一定变成重节点)。所以势能函数满足\(\Delta \phi (i)<l_a+l_b-h_a-h_b\)

而轻节点个数满足\(l_a,l_b<O(\log(N))\)

则有\(\hat c_i<l_a+l_b+h_a+h_b+l_a+l_b-h_a-h_b=2(l_a+l_b)=O(\log(N))\)

\(\sum c_i=\sum \hat c_i+\phi(0)-\phi(n)<N+N\log N\)

实际表现

在P3377中只比左偏树慢了40ms,表现看起来不错

~~总感觉skew heap是写leftist heap忘了写高度判断结果无意发现的数据结构~~

~~大家写代码时多多出错，说不定你就是下一个数据结构发明者~~

• 注:在删除节点时注意写法： cpp fa[x]=fa[lc[x]]=fa[rc[x]]=merge(lc[x],rc[x]); //注意fa[x]有必要改，因为并查集有可能会经过x,尽管他已经被打上了标记（并查集本身难以删掉某个节点）