在这里，我们将了解什么是区间堆。区间堆是完全二叉树，其中除了最后一个节点之外，每个节点都包含两个元素。设节点 P 中两个元素的优先级分别为 'a' 和 'b'。这里我们考虑 a ≤ b。我们说节点 P 代表闭区间 [a, b]。这里 a 是 P 区间的左端点，b 是右端点。当且仅当 a ≤ c ≤ d ≤ b 时，[c, d] 包含在区间 [a, b] 中。在一个……阅读更多

在这里，我们将了解不同的最大 WBLT 操作。HBLT 有不同的操作，例如插入、删除和初始化。它们与 WBLT 也非常相似。但是，合并操作可以在单个自顶向下的过程中完成。WBLT 可以进行单次遍历合并操作。因为我们可以在向下遍历的过程中找到 w 值。我们可以更新 w 值并根据需要交换子树。对于 HBLT，我们无法在向下遍历树的过程中找到 s 值。由于合并可以在单个自顶向下的过程中完成，那么插入和删除……阅读更多

在这里，我们将了解左倾树的另一种变体。在这里，我们将考虑子树中的节点数，而不是从根节点到外部节点的最短路径的长度。在这里，我们将定义节点 x 的权重 w(x)，它是以 x 为根的子树中内部节点的数量。如果 x 是外部节点，则权重为 0。如果 x 是内部节点，则权重比其子节点权重之和多一。以下是加权左倾树 (WBLT) 的示例：假设二叉树是……阅读更多

从最大或最小 HBLT 删除任意节点不是优先队列或 HBLT 的标准操作。如果我们想从 HBLT 中删除一个节点，例如 K，我们必须遵循以下规则。将以 K 为根的子树从树中分离，并将其替换为 K 节点子树的合并结果。更新从 K 到根的路径上的 s 值，并根据需要在此路径上交换子树以保持 HBLT 的属性。要更新从 K 到根的 s 值，我们需要每个节点的父指针。此更新 s 的操作……阅读更多

当数组存储随时间变化的数据时，数组表示法基本上是浪费空间的。为了存储一些数据，我们分配一些足够大的空间来在一个数组中存储多个值。假设我们使用数组加倍标准来增加数组的大小。考虑当前数组大小为 8192。已满。因此，我们需要使用数组加倍技术来增加它。因此，新的数组大小将为 16384。然后将 8192 个元素从旧数组复制到新数组，然后释放旧数组。现在我们可以意识到，在释放……阅读更多

合并策略很容易使用递归来完成。假设 A 和 B 是将要合并的两个 HBLT。如果其中一个是空的，则只需将另一个作为最终结果。如果没有空的 HBLT，那么我们必须比较两个根元素。具有较大元素的根成为合并后的 HBLT 的根。假设 A 具有较大的根。并且它的左子树是 L。假设 C 是合并 A 的右子树和 HBLT B 的结果的最大 HBLT。最终的 HBLT 将以 A 为根，……阅读更多

在最大 HBLT 中，根位于根处。如果根被删除，则将分离两个最大 HBLT，即左子树和右子树。通过再次合并这两个最大 HBLT，我们可以将它们合并为一个。因此，合并后将包含所有元素，除了已删除的那个。

可以使用最大合并操作将元素插入最大 HBLT。此操作用于将两个最大 HBLT 合并为一个最大 HBLT。假设我们要将 x 插入一个名为 H 的最大 HBLT 中。我们将使用 x 创建一个小的 HBLT，然后将其与 H 合并，然后合并后，H 将包含包括 x 在内的所有元素。因此，需要合并操作来执行 HBLT 的插入操作。

在这里，我们将了解什么是高度平衡左倾树 (HBLT)。考虑一个二叉树，其中一个特殊的节点（称为外部节点）替换每个空子树。所有其他节点称为内部节点。当一些外部节点与一些二叉树一起添加时，则称为扩展二叉树。如果我们不考虑该树的叶边，则那是实际的二叉树，而这是扩展二叉树。现在假设 s(x) 是从节点 x 到其子树中外部节点的最短路径的长度。如果 x 是……阅读更多

在这里，我们将了解什么是无环有向图。无环有向图是不包含有向环的有向图。有向无环图缩写为 DAG。每个有限 DAG 至少有一个出度为 0 的节点。只有一个节点的 DAG 示例：有两个节点的 DAG 示例：有三个节点的 DAG 示例：