最小-最大堆被定义为一个完全二叉树，包含交替的最小（或偶数）和最大（或奇数）层级。偶数层级例如 0、2、4 等，奇数层级例如 1、3、5 等。在接下来的要点中，我们认为根元素位于第一层级，即 0。最小-最大堆示例最小-最大堆的特性每个最小-最大堆中的节点都与一个数据成员（通常称为键）相关联，其值用于计算最小-最大堆中节点的顺序。根元素是... 阅读更多

Deap 被定义为一种数据结构，其根节点没有元素或键值。它是通过实现以下规则形成的：根节点没有元素，表示根节点为空。Deap 的左子树应表示最小堆。Deap 的右子树应表示最大堆。因此，可以通过 Deap 结构以数学方式提供以下语句的正确性：如果某个节点的左子树和右子树非空，并且它们的对应节点可以分别表示为“a”和“b”，则：-a.KeyValue

双端优先队列 (DEPQ) 或区间堆具有以下操作：isEmpty()此函数用于检查 DEPQ 是否为空，如果为空则返回 true。size()此函数用于返回 DEPQ 中存在的元素总数。getMin()此函数用于返回具有最低优先级的元素。getMax()此函数用于返回具有最高优先级的元素。put(z)此函数用于将元素 z 插入 DEPQ。removeMin()此函数用于删除具有最小优先级的元素并返回此元素。removeMax()此函数用于删除具有最高优先级的元素并返回此元素。操作 isEmpty()、size()、getMin() 和 getMax() 消耗 O(1)... 阅读更多

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

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

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

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

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

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

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