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