Treap

简介

Treap is Tree + Heap, each node have two property : Key, and Priority.
Using key can format the Binary tree, and using Priority can make a heap.

代码

struct Treap {
    int key,pri;
    int cnt;
    Treap *lc,*rc;
    Treap(int _key) {
        key = _key;
        pri=rand();
        cnt=1;
        lc=rc=NULL;
    };
}*root=NULL;
void cw(Treap* &p) {
    Treap *t=p->lc;
    p->lc = t->rc;
    t->rc = p;
    p->cnt = (p->lc?p->lc->cnt:0) + (p->rc?p->rc->cnt:0) + 1;
    t->cnt = (t->lc?t->lc->cnt:0) + p->cnt + 1;
    p = t;
}
void ccw(Treap* &p) {
    Treap *t=p->rc;
    p->rc = t->lc;
    t->lc = p;
    p->cnt = (p->lc?p->lc->cnt:0) + (p->rc?p->rc->cnt:0) + 1;
    t->cnt = p->cnt + (t->rc?t->rc->cnt:0) + 1;
    p = t;
}
void insert(Treap* &p,int key) {
    if (!p) {
        p = new Treap(key);
        return ;
    }
    p->cnt++;
    if (key < p->key) {
        insert(p->lc, key);
        if (p->lc->pri < p->pri)
            cw(p);
    }
    else {
        insert(p->rc, key);
        if (p->rc->pri < p->pri)
            ccw(p);
    }
}
void remove(Treap* &p,int key) {
    if (p->key < key) {
        p->cnt--;
        return remove(p->rc, key);
    }
    if (key < p->key) {
        p->cnt --;
        return remove(p->lc, key);
    }
    if (p->lc && p->rc) {
        if (p->lc->pri < p->rc->pri)
            cw(p), remove(p->rc, key);
        else
            ccw(p), remove(p->lc, key);
        p->cnt--;
    }else if (p->lc) {
        Treap *t=p->lc;
        delete p;
        p=t;
    }else if (p->rc) {
        Treap *t=p->rc;
        delete p;
        p=t;
    }else {
        delete p;
        p=NULL;
    }
}
int smallCount(Treap *p, int key) {
    if (!p)
        return 0;
    if (key < p->key)
        return smallCount(p->lc, key);
    else
        return (p->lc?p->lc->cnt:0) + 1 + smallCount(p->rc, key);
}
void preorder(Treap *p) {
    if (!p)
        return ;
    cout<<"["<<p<<"] "<<p->key<<" pri="<<p->pri<<"  child{"<<p->lc<<", "<<p->rc<<"}"<<endl;
    preorder(p->lc);
    preorder(p->rc);
}