区间堆与嵌入式最小-最大堆相同，其中每个节点包含两个元素。它被定义为一棵完全二叉树，其中：左侧元素小于或等于右侧元素。两个元素都定义一个闭区间。除根节点之外的任何节点所表示的区间都是其父节点的子区间。左侧元素表示最小堆。右侧元素表示最大堆。根据元素数量，允许两种情况：偶数个元素：在这种情况下，每个节点包含两个元素…… 阅读更多

在区间堆中，最小元素是根节点左侧的元素。此元素将被移除并返回。为了填补根节点左侧产生的空缺，将从最后一个节点移除一个元素，并将其再次插入到根节点。然后，将此元素与下降节点的所有左侧元素依次比较，当满足区间堆的所有条件时，该过程终止。如果节点中的左侧元素大于右侧元素…… 阅读更多

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

对称最小-最大堆 (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) - 创建一个新的软堆 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 最小生成树算法等算法的“可靠选择”，并支持以下操作（假设最小堆）：find-min - 此函数负责返回堆的顶部元素。meld - 此函数负责比较两个根元素，较小的元素保持结果的根，较大的元素及其子树作为子节点添加…… 阅读更多