左偏樹

图解数据结构（9）——左偏树

十三、左偏树（Leftist Tree）
树这个数据结构内容真的很多，上一节所讲的二叉堆，其实就是一颗二叉树，这次讲的左偏树（又叫“左翼堆”），也是树。
二叉堆是个很不错的数据结构，因为它非常便于理解，而且仅仅用了一个数组，不会造成额外空间的浪费，但它有个缺点，那就是很难合并两个二叉堆，对于“合并”，“拆分”这种操作，我觉得最方面的还是依靠指针，改变一下指针的值就可以实现，要是涉及到元素的移动，那就复杂一些了。
左偏树跟二叉堆比起来，就是一棵真正意义上的树了，具有左右指针，所以空间开销上稍微大一点，但却带来了便于合并的便利。BTW：写了很多很多的程序之后，我发觉“空间换时间”始终是个应该考虑的编程方法。:)
左偏左偏，给人感觉就是左子树的比重比较大了，事实上也差不多，可以这么理解：左边分量重，那一直往右，就一定能最快地找到可以插入元素的节点了。所以可以这样下个定义：左偏树就是对其任意子树而言，往右到插入点的距离（下面简称为“距离”）始终小于等于往左到插入点的距离，当然了，和二叉堆一样，父节点的值要小于左右子节点的值。

//reference: ACM/ICPC代碼庫  http://ir.hit.edu.cn/~lfwang/docs/MyLib(For%20ACM).pdf
#include<stdio.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

#define N 100

using namespace std;

#define typec int // type of key val
const int na = -1;
struct node { typec key; int l, r, f, dist; } tr[N];
int iroot(int i){ // find i's root
    if (i == na) return i;
    while (tr[i].f != na) i = tr[i].f;
    return i;
}
int merge(int rx, int ry){ // two root: rx, ry
    if (rx == na) return ry;
    if (ry == na) return rx;
    if(DBG)printf("merge %d %d\n",rx,ry);
    if (tr[rx].key > tr[ry].key)swap(rx, ry);
    int r = merge(tr[rx].r, ry);
    tr[rx].r = r; tr[r].f = rx;
    if (tr[r].dist > tr[tr[rx].l].dist)
    swap(tr[rx].l, tr[rx].r);
    if (tr[rx].r == na) tr[rx].dist = 0;
    else tr[rx].dist = tr[tr[rx].r].dist + 1;
    if(DBG)printf("root %d(%d)\n",rx,tr[rx].key);
    return rx; // return new root
}
int del(int i) { // delete node i
    if (i == na) return i;
    int x, y, l, r;
    l = tr[i].l; r = tr[i].r; y = tr[i].f;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[x = merge(l, r)].f = y;
    if (y != na && tr[y].l == i) tr[y].l = x;
    if (y != na && tr[y].r == i) tr[y].r = x;
    for ( ; y != na; x = y, y = tr[y].f) {
        if (tr[tr[y].l].dist < tr[tr[y].r].dist)
        swap(tr[y].l, tr[y].r);
        if (tr[tr[y].r].dist + 1 == tr[y].dist) break;
        tr[y].dist = tr[tr[y].r].dist + 1;
        }
        if (x != na) return iroot(x); // return new root
        else return iroot(y);
    }
node top(int root){
    return tr[root];
}
node pop(int &root){
    node out = tr[root];
    int l = tr[root].l, r = tr[root].r;
    tr[root].l = tr[root].r = tr[root].f = na;
    tr[l].f = tr[r].f = na;
    root = merge(l, r);
    return out;
}
int ins(int i, typec key, int &root){ // add a new node(i, key)
    tr[i].key = key;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[i].dist = 0;
    if(DBG)printf("ins %d %d\n",i,key);
    return root = merge(root, i); // return new root
}
int add(int i, typec val) // tr[i].key += val
{
    if (i == na) return i;
    if (tr[i].l == na && tr[i].r == na && tr[i].f == na) {
        tr[i].key += val;
        return i;
    }
    typec key = tr[i].key + val;
    int rt = del(i);
    return ins(i, key, rt);
}
void init(int n){
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tr[i].key); //%d: type of key
        tr[i].l = tr[i].r = tr[i].f = na;
        tr[i].dist = 0;
    }
    if(DBG)printf("end of init\n");
}
int main(){
    int root=1;
    node n;
    init(1);
    REP(i,2,11)ins(i,i,root);
    rep(i,10)printf("pop %d\n",pop(root).key);
}