找到 346 篇文章 关于数据结构算法

最小-最大堆

Arnab Chakraborty
更新于 2020年1月3日 05:32:36

6K+ 次浏览

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

数据结构中的Deap

Arnab Chakraborty
更新于 2020年1月3日 05:35:07

2K+ 次浏览

Deap 定义为一种数据结构,其根节点没有元素或键值。它是通过实现以下规则形成的:根节点没有元素,表示根节点为空。Deap 的左子树应表示最小堆。Deap 的右子树应表示最大堆。因此,可以通过 Deap 结构对以下语句的正确性进行数学证明:如果某个节点的左子树和右子树非空,并且它们的相应节点分别用 ‘a’ 和 ‘b’ 表示,则 -a.键值

区间堆操作的复杂度

Arnab Chakraborty
更新于 2020年1月3日 05:27:43

165 次浏览

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

初始化区间堆

Arnab Chakraborty
更新于 2020年1月3日 05:26:34

246 次浏览

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

从区间堆中删除最小元素

Arnab Chakraborty
更新于 2020年1月2日 07:55:44

308 次浏览

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

在区间堆中插入元素

Arnab Chakraborty
更新于 2020年1月2日 07:54:12

183 次浏览

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

对称最小-最大堆

Arnab Chakraborty
更新于 2020年7月13日 07:15:03

1K+ 次浏览

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

双端优先队列 (DEPQ)

Arnab Chakraborty
更新于 2020年1月2日 07:49:18

2K+ 次浏览

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

软堆

Arnab Chakraborty
更新于 2020年1月2日 07:26:18

357 次浏览

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

配对堆的自适应特性

Arnab Chakraborty
更新于 2020年1月2日 07:10:45

114 次浏览

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

广告