如何用(平衡树)WBLT 实现可并堆?
  • 板块学术版
  • 楼主jifbtDinshey
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/11/10 11:48
  • 上次更新2023/10/27 03:32:54
查看原帖
如何用(平衡树)WBLT 实现可并堆?
103171
jifbtDinshey楼主2022/11/10 11:48

在学习平衡树时,我在 OI Wiki 上看到对 WBLT 的描述:

WBLT,全称 Weight Balanced Leafy Tree,一种不常见的平衡树写法,但是具有常数较小,可以当做 可并堆 使用的优点。

因为 WBLT 同时满足堆的性质,我们可以用它来实现堆和可并堆。

原文并未给出实现可并堆的方法;在网络上也找不到结果。如果直接套用左偏树的合并方法,则不满足平衡树性质。

有另一个数据结构“重量优先左偏树”(Weight-biased Leftist Tree,即将左偏树中的 dist 定义为子树的大小)也叫 WBLT。我猜想可能是 OI Wiki 的编者混淆了这两种数据结构。

那么,WBLT 究竟可不可以实现可并堆,实现的方法是什么?

2022/11/10 11:48
加载中...