现在的位置: 首页 > 综合 > 正文

左偏树(可并堆)

2018年12月19日 ⁄ 综合 ⁄ 共 1409字 ⁄ 字号 评论关闭

左偏树(Leftist Tree)是一种可并堆

外节点:是一个左子树为空或者右子树为空的节点
节点的距离dist:为它到它子树内外节点的最短距离
左偏树满足下面两条基本性质:
     [性质1] 节点的键值小于或等于它的左右子节点的键值
  [性质2] 节点的左子节点的距离不小于右子节点的距离


学习资料:

    国外论文:http://www.dgp.toronto.edu/people/JamesStewart/378notes/10leftist/

    图解数据结构(9)——左偏树:http://www.cnblogs.com/yc_sunniwell/archive/2010/06/28/1766756.html

=====================================================
基本操作:
int Init(int x)
输入: x 单节点左偏树的权值
输出:新建的左偏树的编号

int Insert(int x, int y)
输入:x,y 向编号为x的左偏树中插入一个权值为y的节点
输出:新的堆顶编号

int Top(int x)
复杂度:O(1)
输入:x 左偏树的编号
输出:编号为x的左偏树的堆顶的权值

int Pop(int x)
复杂度:O(logn)
输入: x 左偏树的编号
输出:删除编号为x的左偏树的堆顶,返回新的堆顶编号

int Merge(int x, int y)
复杂度:O(logn)
输入:x,y 要合并的两棵左偏树的编号
输出:新的堆顶编号

const int maxn = 100000; //最多节点数
int
tot,  //添加过的节点个数
v[maxn],  //节点键值
l[maxn],  //左节点编号
r[maxn],  //右节点编号
d[maxn];  //节点距离

int Merge(int x, int y)
{
    //如果一棵树为空,我们只须要返回另一棵树
    if(!x)
        return y;
    if(!y)
        return x;

    //如果x的根节点的键值小于y根节点的,则交换x,y
    if(v[x] < v[y])
        swap(x,y);

    //把x作为新树,合并x的右子树right(x)和y
    r[x] = Merge(r[x], y);

    //合并后,如果右子树right(x)的距离大于左子树left(x)则交换左右子树
    if ( d[l[x]] < d[r[x]])
        swap(l[x], r[x]);

    //最后更新根节点的距离值
    d[x] = d[r[x]] + 1;
    return x;
}

int Init(int x)
{
    tot++;
    v[tot] = x;
    l[tot] = r[tot] = d[tot] = 0;
}

int Insert(int x, int y)
{
    //插入一个节点可以看作是对两棵左偏树的合并
    return Merge(x,Init(y));
}

int Top(int x)
{
    return v[x];
}
int Pop(int x)
{
    return Merge(l[x],r[x]);
}

练习题:


ZOJ2334 Monkey King       解题报告


HDU1434 幸福列车      入门题


ZOJ3512
SEQUENCE 
数字序列 

 (http://blog.163.com/hacker_james/blog/static/659024432011711105241183/)


《​左​偏​树​的​特​点​及​其​应​用​》 --黄源河http://wenku.baidu.com/view/68c27b21af45b307e87197af.html?re=view

【上篇】
【下篇】

抱歉!评论已关闭.