初始化区间堆

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

  • 左元素小于或等于右元素。
  • 这两个元素都定义了一个闭区间。
  • 除根节点外的任何节点所表示的区间都是父节点的子区间。
  • 左侧的元素表示最小堆。
  • 右侧的元素表示最大堆。

根据元素的数量，允许两种情况：

  • 偶数个元素：在这种情况下，每个节点包含两个元素，例如 a 和 b，其中 a ≤ b。然后每个节点都由区间 [a, b] 表示。
  • 奇数个元素：在这种情况下，除最后一个节点外的每个节点都包含两个元素，由区间 [a, b] 表示，而最后一个节点将包含单个元素，并由区间 [a, b] 表示。

可以使用与初始化普通堆相同的策略来初始化区间堆——从堆底到根依次处理，确保每个子树都被表示为区间堆。对于每个子树，首先对根节点中的元素进行排序；然后再次插入此子树根节点的左端点，实现用于 removeMin 函数的重新插入策略，然后再次插入此子树根节点的右端点，实现用于 removeMax 函数的策略。

更新于： 2020年1月3日

243 次浏览

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告