从间隔堆中删除最小元素
在间隔堆中，最小的元素是根节点左侧的元素。该元素被消除并返回。
为了填补在根节点左侧创建的空缺，消除了最后一个节点中的元素，然后再次将其插入到根节点中。
接下来，将该元素与降序节点的所有左手元素进行连续比较，并在满足间隔堆的所有条件时终止该过程。
如果节点中的左侧元素在任何阶段都变得高于右侧元素，则交换这两个元素，然后执行进一步的比较。
最后，根节点将再次在左侧包含最小的元素。
也可以通过以下方式解释此过程-
删除最小元素的方法有以下几种：
当间隔堆为空时，removeMin操作将失败。
当间隔堆只有一个元素时，应返回此元素。我们留下没有任何元素的间隔堆。
如果有多个元素，则应返回根的左端点。从根本上消除了这一点。
如果根节点指示间隔堆的最后一个节点，则无需执行其他任何操作。
当最后一个节点不是根节点时，我们从最后一个节点中消除左点p。如果这导致最后一个节点空闲，则最后一个节点不再是堆的一部分。
通过从根节点开始，将从最后一个节点消除的点p重新插入到嵌入式min堆中。
当我们向下移动时，可能有必要将电流p与被检查节点的右端点r交换，以确保p≤r。执行重新插入时所执行的策略与重新插入普通堆时所用的策略相同。
以上是 从间隔堆中删除最小元素 的全部内容， 来源链接： utcz.com/z/356771.html
