初始化间隔堆

间隔堆与嵌入式最小-最大堆相同,其中每个节点包含两个元素。它被定义为一个完整的二叉树,其中

  • 左元素小于或等于右元素。

  • 这两个元素都定义了一个封闭的间隔。

  • 除根以外的任何节点表示的间隔是父节点的子间隔。

  • 左侧的元素表示最小堆。

  • 右侧的元素代表最大堆。

根据元素的数量,允许两种情况-

  • 偶数个元素:在这种情况下,每个节点包含两个元素,例如a和b,且a≤b。然后,每个节点都由间隔[a,b]表示。

  • 奇数个元素:在这种情况下,除最后一个节点外,每个节点都包含两个由间隔[a,b]表示的元素,而最后一个节点将包含一个元素,并由间隔[a,b]表示。

可以使用与初始化普通堆相同的策略来初始化间隔堆-从堆底部到根的工作方式确保每个子树都表示为间隔堆。对于每个子树,首先对根中的元素进行排序;然后再次插入此子树的根的左端点,以实现用于removeMin函数的重新插入策略,然后再次插入此子树的根的右端点,以实现用于removeMax函数的策略。

以上是 初始化间隔堆 的全部内容, 来源链接: utcz.com/z/347210.html

回到顶部