认识达内从这里开始

随着互联网的不断发展，越来越多的人都在学习Java编程开发语言，而本文我们就通过案例分析来简单了解一下，Java编程入门需要掌握哪些数据结构。

一、堆(Heaps)

小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]<=val[x]，具有堆的xa节点，其中val[x]是它的值，par[x]是它的父级。

还有一个实现相反关系的大堆。

二叉堆是一棵完整的二叉树(它的所有层都被填充，除了后一层)。

它们是做什么用的?

正如我们几天前讨论过的，优先队列可以使用二叉堆有效地实现，因为它支持O(logn)时间内的insert()、delete()、extractMax()和reduceKey()操作。这样，堆在图算法中也是必不可少的(因为优先级队列)。

任何时候您需要快速访问大/小项目，堆都是好的选择。

堆也是堆排序算法的基础。

特性

它总是平衡的：无论何时我们在结构中删除/插入一个元素，我们只需要“筛选”/“渗透”它直到它处于正确的位置;

节点k>1的父节点是[k/2](其中[x]是x的整数部分)，其子节点是2k和2k+1;

设置优先级队列的替代方案，ordered_map(在C++中)或任何其他可以轻松允许访问小/大元素的有序结构;

根优先，因此其访问的时间复杂度为O(1)，插入/删除在O(logn)中完成;创建一个堆是在O(n)中完成的;O(n*logn)中的堆排序。

二、字典树(Tries)

trie是一种高效的信息检索数据结构。也称为前缀树，它是一种搜索树，允许以O(L)时间复杂度插入和搜索，其中L是键的长度。

如果我们将密钥存储在一个平衡良好的BST中，它将需要与L*logn成正比的时间，其中n是树中的密钥数量。这样，与BST相比，trie是一种更快的数据结构(使用O(L))，但代价是trie存储要求。

它们是做什么用的?

树主要用于存储字符串及其值。它酷的应用程序之一是在Google搜索栏中键入自动完成和自动建议。特里是好的选择，因为它是快的选择：如果我们不使用特里，更快的搜索比节省的存储更有价值。

通过在字典中查找单词或在同一文本中查找该单词的其他实例，也可以使用trie来完成键入单词的正字法自动更正。

特性

它有一个键值关联;键通常是一个单词或它的前缀，但它可以是任何有序列表;

根有一个空字符串作为键;

节点值与其子节点值之间的长度差为1;这样，根的子节点将存储长度为1的值;作为结论，我们可以说来自k层的节点x具有长度k的值;

正如我们所说，插入/搜索操作的时间复杂度是O(L)，其中L是键的长度，这比BST的O(logn)快得多，但与哈希表相当;

空间复杂度实际上是一个缺点：O(ALPHABET_SIZE*L*n)。

三、段树(SegmentTrees)

段树是一个完整的二叉树，可以有效地回答查询，同时仍然可以轻松修改其元素。

给定数组中索引i上的每个元素代表一个用[i,i]间隔标记的叶子。将其子节点分别标记为[x,y]或[y,z]的节点将具有[x,z]区间作为标签。因此，给定n个元素(0-indexed)，线段树的根将被标记为[0,n-1]。

它们是做什么用的?

它们在可以使用分而治之(我们将要讨论的一个算法概念)解决的任务中非常有用，并且还可能需要更新其元素。这样，在更新元素时，包含它的任何区间也会被修改，因此复杂度是对数的。例如，n个给定元素的总和/大值/小值是线段树常见的应用。如果元素更新正在发生，二分搜索也可以使用段树。

特性

作为二叉树，节点x将2x和2x+1作为子节点，[x/2]作为父节点，其中[x]是x的整数部分;

更新段树中整个范围的一种有效方法称为“延迟传播”，它也是在O(logn)中完成的(有关操作的实现，请参见下面的链接);

它们可以是k维的：例如，有q个查询来查找一个矩阵的给定子矩阵的总和，我们可以使用二维线段树;

更新元素/范围需要O(logn)时间;对查询的回答是恒定的(O(1));

空间复杂度是线性的，这是一个很大的优势：O(4*n)。

四、树状数组(FenwickTrees)

fenwick树，也称为二叉索引树(BIT)，是一种也用于高效更新和查询的数据结构。与SegmentTrees相比，BITs需要更少的空间并且更容易实现。

它们是做什么用的?

BIT用于计算前缀和——i个位置的元素的前缀和是从一个位置到i个元素的总和。它们使用数组表示，其中每个索引都以二进制系统表示。例如，索引10相当于十进制系统中的索引2。

特性

树的构建是有趣的部分：先，数组应该是1-indexed要找到节点x的父节点，您应该将其索引x转换为二进制系统并翻转右边的有效位;ex.节点6的父节点是4;

6=1*2²+1*2¹+0*2⁰=>1"1"0(flip)

=>100=1*2²+0*2¹+0*2⁰=4;

后，ANDing元素，每个节点都应该包含一个可以添加到前缀和的间隔;

更新的时间复杂度仍然是O(logn)，查询的时间复杂度仍然是O(1)，但空间复杂度与线段树的O(4*n)相比是一个更大的优势：O(n)。

五、并查集(DisjointSetUnion)

我们有n个元素，每个元素代表一个单独的集合。并查集(DSU)允许我们做两个操作：

1.UNION—组合任意两个集合(或者统一两个不同元素的集合，如果它们不是来自同一个集合);

2.FIND—查找元素来自的集合。

它们是做什么用的?

并查集(DSU)在图论中非常重要。您可以检查两个顶点是否来自同一个连接组件，或者甚至可以统一两个连接组件。

让我们以城市和城镇为例。由于人口和经济增长的邻近城市正在扩张，它们可以轻松创建大都市。因此，两个城市合并在一起，他们的居民住在同一个大都市。我们还可以通过调用FIND函数来检查一个人居住在哪个城市。

特性

它们用树表示;一旦两组组合在一起，两个根中的一个成为主根，另一个根的父代是另一棵树的叶子之一;

一种实用的优化是通过高度压缩树木;这样，联合由大的树组成，以轻松更新它们的两个数据(参见下面的实现);

所有操作都在O(1)时间内完成。

六、小生成树(MinimumSpanningTrees)

给定一个连通图和无向图，该图的生成树是一个子图，它是一棵树并将所有节点连接在一起。单个图可以有许多不同的生成树。加权、连通和无向图的小生成树(MST)是权重(成本)小于或等于其他所有生成树权重的生成树。生成树的权重是赋予生成树每条边的权重之和。

它们是做什么用的?

小生成树(MST)问题是一个优化问题，一个小成本问题。有了路线网，我们可以认为影响n个城市之间建立国道的因素之一是相邻两个城市之间的小距离。

国家路线就是这样，由道路网络图的MST表示。

特性

作为一棵树，具有n个顶点的图的MST具有n-1条边;可以使用以下方法解决：

Prim算法—密集图的佳选择(具有n个节点且边数接近n(n-1)/2)的图);

Kruskal算法——主要使用;它是一种基于不相交集联合的贪心算法(我们后面也将讨论它);

构建它的时间复杂度对于Kruskal来说是O(nlogn)或O(nlogm)(这取决于图)，对于Prim来说是O(n²)。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei456学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。