【数据结构】二叉堆与左偏树

// 二叉堆
void up( int i )
{
    int dad = i >> 1,data = heap[i];
    while( dad != 0 && heap[dad] > data )
    {
        heap[i] = heap[dad];
        i = dad;
        dad = i >> 1;
    }
    heap[i] = data;
}

void down( int i )
{
    int son = i << 1,data = heap[i];
    while( son <= sum )
    {
        if( son < sum && heap[son] > heap[son+1] ) son++;
        if( heap[son] >= data ) break;
        heap[i] = heap[son];
        i = son;
        son = i << 1;
    }
    heap[i] = data;
}

// 左偏树
int merge( int aa,int bb )
{
    if( !aa ) return bb;
    if( !bb ) return aa;
    if( key[aa] > key[bb] ) swap( aa,bb );
    rt[aa] = merge( rt[aa],bb );
    if( dis[ rt[aa] ] > dis[ lt[aa] ] ) swap( rt[aa],lt[aa] );
    if( !rt[aa] ) dis[aa] = 0; else dis[aa] = dis[ rt[aa] ] + 1;
    return a;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!