0001 template <typename T> //合并以a和b为根节点的两个左式堆（迭代版）
0002 BinNodePosi<T> merge( BinNodePosi<T> a, BinNodePosi<T> b ) {
0003    if ( !a ) return b; //退化情况
0004    if ( !b ) return a; //退化情况
0005    if ( lt( a->data, b->data ) ) swap( a, b ); //确保a>=b
0006    for ( ; a->rc; a = a->rc ) //沿右侧链做二路归并，直至堆a->rc先于b变空
0007       if ( lt( a->rc->data, b->data ) ) //只有在a->rc < b时才需做实质的操作
0008          { b->parent = a; swap( a->rc, b ); } //接入b的根节点（及其左子堆）
0009    ( a->rc = b )->parent = a; //直接接入b的残余部分（必然非空）
0010    for ( ; a; b = a, a = a->parent ) { //从a出发沿右侧链逐层回溯（b == a->rc）
0011       if ( !a->lc || ( a->lc->npl < a->rc->npl ) ) //若有必要
0012          swap( a->lc, a->rc ); //通过交换确保右子堆的npl不大
0013       a->npl = a->rc ? a->rc->npl + 1 : 1; //更新npl
0014    }
0015    return b; //返回合并后的堆顶
0016 } //本算法只实现结构上的合并，堆的规模须由上层调用者负责更新