在学习平衡树时,我在 OI Wiki 上看到对 WBLT 的描述:
WBLT,全称 Weight Balanced Leafy Tree,一种不常见的平衡树写法,但是具有常数较小,可以当做 可并堆 使用的优点。
因为 WBLT 同时满足堆的性质,我们可以用它来实现堆和可并堆。
原文并未给出实现可并堆的方法;在网络上也找不到结果。如果直接套用左偏树的合并方法,则不满足平衡树性质。
有另一个数据结构“重量优先左偏树”(Weight-biased Leftist Tree,即将左偏树中的 dist 定义为子树的大小)也叫 WBLT。我猜想可能是 OI Wiki 的编者混淆了这两种数据结构。
那么,WBLT 究竟可不可以实现可并堆,实现的方法是什么?