0001 template <typename T> BNP<T> meld(BNP<T> a, BNP<T> b) { //左式堆的融合(递归版) 0002 if (!a) return b; if (!b) return a; //退化情况 0003 if (*a < *b) swap(a, b); //确保a>=b 0004 (a->rc = meld(a->rc, b))->parent = a; //将a的右子堆,与b融合 0005 if (NPL(a->lc) < NPL(a->rc)) //若有必要(宏隐藏了边界情况) 0006 swap(a->lc, a->rc); //通过flip确保右子堆的npl不大 0007 a->npl = NPL(a->rc) + 1; //更新a的npl(宏隐藏了边界情况) 0008 return a; //返回融合后的堆顶 0009 } //本算法只实现结构上的融合,堆的规模须由上层调用者负责更新