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

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

在这里我们将看到左倾树的另一种变体。在这里，我们将考虑子树中的节点数，而不是从根节点到外部节点的最短路径的长度。在这里，我们将定义节点 x 的权重 w(x)，为以 x 为根的子树中的内部节点数。如果 x 是外部节点，则权重为 0。如果 x 是内部节点，则权重比其子节点权重之和多 1。下面是一个加权左倾树 (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 示例 -