取决于区间堆中存在的元素数量，可能有以下几种情况：奇数个元素：如果区间堆中的元素个数为奇数，则新元素首先插入到最后一个节点。然后，它会连续与前面的节点元素进行比较，并测试其是否满足区间堆的基本条件。如果元素不满足任何条件，则将其从最后一个节点转移到根节点，直到满足所有条件。偶数个元素：如果元素个数为偶数……阅读更多

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

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

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

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

计算合并操作的摊销成本是一项困难的任务。主要困难在于累积在操作序列不同点执行的操作成本的巨大差异。尽管我们的设计目标受到操作序列成本的影响，但根据操作序列的成本来定义操作的摊销成本的概念却毫无意义。实现一个潜在函数来抵消实际成本的差异是处理这种情况的完美方法。在下一个主题中，我们将讨论摊销……阅读更多

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

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

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

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