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

在区间堆中，最小的元素是根节点左侧的元素。此元素被删除并返回。为了填充根节点左侧创建的空缺，最后一个节点中的一个元素被删除并再次插入到根节点中。然后，将此元素依次与下降节点的所有左侧元素进行比较，并且当满足区间堆的所有条件时，该过程终止。如果节点中的左侧元素变得高于右侧元素，则 ... 阅读更多

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

对称最小-最大堆 (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 算法计算图中最短路径时，主要实现优先队列。配对堆很完美，因为它们易于使用并且在实际应用中运行良好。具体来说，它们在摊销时间内运行良好。这意味着虽然单个操作消耗更长的时间，但整个操作序列中所有操作的总和 ... 阅读更多

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

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

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