0001 template <typename T> //根据相对优先级确定适宜的方式,合并以a和b为根节点的两个左式堆 0002 static 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 ); //一般情况:首先确保b不大 0006 ( a->rc = merge ( a->rc, b ) )->parent = a; //将a的右子堆,与b合并 0007 if ( !a->lc || a->lc->npl < a->rc->npl ) //若有必要 0008 swap ( a->lc, a->rc ); //交换a的左、右子堆,以确保右子堆的npl不大 0009 a->npl = a->rc ? a->rc->npl + 1 : 1; //更新a的npl 0010 return a; //返回合并后的堆顶 0011 } //本算法只实现结构上的合并,堆的规模须由上层调用者负责更新