从区间堆中移除最小元素

  • 在区间堆中，最小元素位于根节点的左侧。该元素被移除并返回。
  • 为了填补根节点左侧创建的空缺，从最后一个节点移除一个元素，并再次插入到根节点。
  • 然后，将此元素依次与所有下降节点的左侧元素进行比较，当满足区间堆的所有条件时，该过程终止。
  • 如果在任何阶段节点中的左侧元素变得高于右侧元素，则交换这两个元素，然后执行进一步的比较。
  • 最后，根节点将再次包含左侧的最小元素。

此过程也可以用以下方式解释 -

最小元素的移除可以通过多种方式处理 -

  • 当区间堆为空时，removeMin 操作失败。
  • 当区间堆只有一个元素时，应返回此元素。我们留下一个没有任何元素的区间堆。
  • 当存在多个元素时，应返回根的左端点。此点从根中移除。
  • 如果根指示区间堆的最后一个节点，则无需执行更多操作。
  • 当最后一个节点不是根节点时，我们从最后一个节点移除左端点 p。如果这导致最后一个节点变为空，则最后一个节点不再是堆的一部分。
  • 从最后一个节点移除的点 p 通过从根开始重新插入到嵌入的最小堆中。
  • 当我们向下移动时，可能需要将当前 p 与正在检查的节点的右端点 r 交换，以确保 p ≤r。重新插入是通过实现与重新插入普通堆相同的策略来执行的。

更新于: 2020年1月2日

308 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告