可合并双端优先队列 (Meldable DEPQs)

  • 可合并双端优先队列 (MDEPQ) 定义为双端优先队列 (DEPQ)，除了上面列出的 DEPQ 操作外，还包括操作 meld(p, q) ... 将 DEPQ p 和 q 合并成单个 DEPQ。合并双端优先队列 p 和 q 的结果是一个包含 p 和 q 所有元素的单个双端优先队列。meld 操作是破坏性的，因为在合并之后，p 和 q 不会保留为独立的 DEPQ。
  • 为了在小于线性时间内合并两个 DEPQ，必须使用显式指针（而不是像堆的数组表示那样使用隐式指针）来表示 DEPQ，否则需要将线性数量的元素从初始位置移动到最终位置。
  • 可以证明，当最小-最大对堆以这种方式表示时，一个大小为 n 的 DEPQ 可以与另一个大小为 k (其中 k<=n) 的 DEPQ 在 O(log(n/k)*log k) 时间内合并。
  • 可以证明，合并大小分别为 a 和 b 的两个最小-最大堆的复杂度为 Ω(a + b)。
  • 一个 MDEPQ 实现允许计算最小和最大元素，插入元素，并在 O(1) 时间内合并两个优先队列。删除最小或最大元素所需的时间为 O(log n)。
  • 可以证明，左倾树可以被改编以获得 MDEPQ 的简单表示，其中合并消耗对数时间，其余操作具有与实现上述任何 DEPQ 表示时相同的渐近复杂度。
  • 有趣的是，如果我们实现 FMPQ（快速可合并优先队列）结构作为基础 MPQ 结构，我们将获得一个完全对应的 MDEPQ 结构，其中 removeMax 和 removeMin 消耗对数时间，其余操作消耗常数时间。与双优先队列自适应相比，这种自适应非常优秀，因为空间需求几乎减少了一半。此外，完全对应的自适应比双优先队列自适应更快。

更新于：2020年1月3日

109 次浏览

启动您的职业生涯

通过完成课程获得认证

开始学习
广告