根据区间堆中存在的元素数量，可能出现以下情况 -奇数个元素：如果区间堆中的元素数量为奇数，则新元素首先插入到最后一个节点。然后，依次将其与前面的节点元素进行比较，并测试其是否满足区间堆所需的条件。如果元素不满足任何条件，则将其从最后一个节点转移到根节点，直到满足所有条件。偶数个元素：如果元素的数量... 阅读更多

对称最小-最大堆 (SMMH) 定义为一棵完全二叉树，其中除根节点外每个节点都只有一个元素。SMMH 的根节点可以为空，SMMH 中的节点总数为 m + 1，其中 m 是元素的数量。令 y 为 SMMH 中的任意节点。令 elements(y) 为以 y 为根的子树中的元素，但不包括 y 中的元素（如果有）。假设 elements(y) j= ∅。y 满足以下属性：y 的左孩子在 elements(y) 中具有最小元素。y 的右孩子... 阅读更多

双端优先队列 (DEPQ) 或双端堆被定义为一种类似于优先队列或堆的数据结构，但允许有效地移除最大值和最小值，根据存储在结构中的键或项目的某种排序。DEPQ 中的每个元素都与一个优先级或值相关联。在 DEPQ 中，可以按升序和降序消除或移除元素。操作双端优先队列包含以下操作isEmpty()此函数负责检查 DEPQ 是否为空，如果为空则返回 true。size()此函数负责返回总... 阅读更多

软堆被定义为简单堆数据结构的一种变体，它包含 5 种操作的常数均摊时间。这是通过仔细“破坏”（增加）堆中最多一定数量的值的键来实现的。常数时间操作为-create(s) - 在软堆 s 中创建一个新的软堆insert(s,  y) - 将元素 y 插入到软堆 s 中meld(s,  s' )将两个软堆 s 和 s′ 合并成一个，销毁两者delete(s,  y) - 从软堆 s 中删除元素 yfindmin(s) - 获取软... 阅读更多

配对堆是为了完美地使用优先队列而实现的。优先队列跟踪一组对象的最小值，因此每次我们从队列中删除某些内容时，它始终是最小值。优先队列主要在使用 Dijkstra 算法计算图中最短路径时实现。配对堆之所以完美，是因为它们易于使用并且在实际应用中运行良好。具体来说，它们在均摊时间内运行良好。这意味着虽然单个操作消耗更长的时间，但整个操作序列中所有操作的总和... 阅读更多

计算合并操作的均摊成本是一项困难的任务。主要困难在于累积在操作序列的不同点执行的操作成本的广泛变化。虽然我们的设计目标受操作序列成本的影响，但根据操作序列成本定义操作的均摊成本的概念毫无意义。实现一个势函数来抵消实际成本的变化是处理这种情况的完美方法。在下一个主题中，我们将讨论均摊... 阅读更多

配对堆可以是空堆，也可以是包含根元素和可能为空的配对堆列表的配对树。堆排序属性需要任何节点的父节点都不大于节点本身。以下描述考虑了一个纯函数堆，它不支持减少键操作。类型 PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]])类型 PairingHeap[Element] = Empty | PairingTree[Element]配对堆存在两种类型——最小配对堆和最大配对堆。当我们希望表示最小优先队列时，实现最小配对堆，而最大配对堆... 阅读更多

配对堆被定义为一种堆数据结构，具有相对简单的实现和极佳的实际均摊性能。配对堆是堆排序的多路树结构，可以表示为简化的斐波那契堆。它们被认为是实现诸如 Prim 的最小生成树算法等算法的“可靠选择”，并支持以下操作（假设为最小堆） -find-min - 此函数负责返回堆的顶部元素。meld -此函数负责比较两个根元素，较小的元素保留为结果的根，较大的元素及其子树作为... 阅读更多

可合并优先队列定义随机可合并堆（也称为可合并堆或随机可合并优先队列）被定义为一种基于优先队列的数据结构，其中底层结构也是一个堆排序的二叉树。但是，关于底层二叉树的形状没有硬性规定。优点这种方法具有一些与类似数据结构相比的便利之处，即优点。它提供了比其他数据结构更简单的方法。随机可合并堆的所有操作都易于应用，并且其复杂度边界中的常数因子很小。也不需要保留平衡条件，也不需要卫星... 阅读更多

生成树一个简单的定义是，树是一个与没有循环相关的连通图，其中循环允许我们从一个节点到自身而不重复边。连通图 G 的生成树定义为包含 G 所有顶点的树。生成树通常用于互联网路由算法。在互联网中，计算机（节点）通常通过许多冗余物理连接连接。图中生成树的总数。如果一个图是具有 n 个顶点的完全图，则生成树的总数为 n(n-2)，其中 n 表示... 阅读更多