在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

TheAlgorithms/Java

菜单

数据结构

相关源文件

本页面全面概述了 TheAlgorithms/Java 仓库中数据结构的实现。这些实现旨在用于教育目的，帮助理解各种数据结构的内部工作原理、属性和应用。有关操作这些数据结构的算法，请参见“算法”部分中的相关页面。

数据结构概述

该仓库包含了按逻辑类别组织的大量数据结构实现。每个实现都附有全面的文档和测试，以演示使用模式和边界情况。

来源

堆实现

堆是满足堆属性的树形数据结构，使其在优先级队列操作中效率很高。

堆类层次结构

来源

最小堆

MinHeap 类实现了一个最小堆，其中每个节点的键都小于或等于其子节点的键。根节点包含最小元素，因此以 O(1) 时间检索最小元素效率很高。

主要功能

  • 支持插入、删除和提取最小元素等基本操作
  • 使用动态数组 (ArrayList) 作为底层存储
  • 通过 toggleUp 和 toggleDown 方法在添加或删除元素时保持堆属性
Time Complexities:
- Get minimum element: O(1)
- Insert element: O(log n)
- Delete element: O(log n)

使用示例

来源

最大堆

MaxHeap 类实现了一个最大堆，其中每个节点的键都大于或等于其子节点的键。根节点包含最大元素，因此以 O(1) 时间检索最大元素效率很高。

主要功能

  • 与 MinHeap 接口几乎相同，但具有相反的排序属性
  • 提供插入、删除和提取最大元素的方法
  • 使用类似的切换机制来保持堆属性
Time Complexities:
- Get maximum element: O(1)
- Insert element: O(log n)
- Delete element: O(log n)

来源

通用堆

GenericHeap 类提供了堆数据结构的通用实现，适用于任何实现 Comparable 接口的类型。

主要功能

  • 存储必须扩展 Comparable 的泛型类型 T 的元素
  • 使用 HashMap 跟踪元素位置以实现高效更新
  • 支持堆中已存在元素的优先级更新

来源

斐波那契堆

FibonacciHeap 类实现了一种更复杂的堆数据结构，在某些操作上具有更好的均摊时间复杂度。它在合并两个堆和减小键值时特别高效。

主要功能

  • 插入和减小键值操作的均摊时间复杂度为 O(1)
  • 删除和提取最小元素操作的均摊时间复杂度为 O(log n)
  • 合并两个斐波那契堆（合并操作）的时间复杂度为 O(1)
  • 使用具有最小堆属性的树的循环链表

来源

最小优先级队列

MinPriorityQueue 类提供了使用最小堆实现的优先级队列。键值最小的元素具有最高优先级，并首先出队。

主要功能

  • 固定大小实现，容量在创建时指定
  • 支持具有优先级排序的标准队列操作（插入、删除、窥视）
  • 包括一个 heapSort 方法，该方法按升序提取所有元素

来源

列表实现

列表是按顺序存储元素的线性数据结构。该仓库包含了各种具有不同特性和操作的链表实现。

列表实现概述

来源

单向链表

SinglyLinkedList 类实现了一个基本的链表，其中每个节点指向序列中的下一个节点。它构成了仓库中许多其他列表操作和扩展的基础。

主要功能

  • 维护头指针和大小计数器
  • 支持在开头、结尾或任何位置的插入和删除操作
  • 包括搜索、计数和循环检测等实用方法
  • 提供迭代和递归方法用于反转等操作

使用示例

时间复杂度

  • 在头部插入/删除：O(1)
  • 在尾部或任意位置插入/删除：O(n)
  • 搜索：O(n)
  • 查找中间元素：O(n)
  • 循环检测：O(n)

来源

反转 K 组

ReverseKGroup 类提供了按 k 个节点一组反转链表中节点的功能。如果剩余节点少于 k 个，则它们保持不变。

示例

Input: 1->2->3->4->5 and k = 3
Output: 3->2->1->4->5

主要功能

  • 使用递归来处理每组的反转
  • 维护组之间的正确连接
  • 当节点数量小于 k 时，防止不必要的反转

来源

旋转单向链表

RotateSinglyLinkedLists 类提供了一种将单向链表向右旋转指定位置数的方法。

示例

Input: 1->2->3->4->5 and k = 2
Output: 4->5->1->2->3

主要功能

  • 处理空列表、单节点列表和零旋转等边界情况
  • 通过使用模运算优化大于列表长度的旋转
  • 临时创建循环列表以高效执行旋转

来源

链表快速排序

QuickSortLinkedList 类实现了单向链表的快速排序算法。它围绕枢轴元素（头部）划分列表，递归地排序子列表，然后将它们组合起来。

主要功能

  • 使用列表的头部作为枢轴元素
  • 为小于和大于枢轴的元素创建单独的列表
  • 递归地排序这些子列表
  • 将排序后的子列表与枢轴组合，形成最终的排序列表

来源

合并已排序单向链表

MergeSortedSinglyLinkedList 类提供了一个静态方法，用于将两个已排序的单向链表合并为一个单独的已排序列表。

使用示例

主要功能

  • 为合并结果创建一个新列表，而不修改输入列表
  • 通过一次遍历两个列表来处理合并
  • 高效地附加来自任一列表的任何剩余节点

来源

缓存实现

缓存是旨在存储常用数据以加快检索速度的数据结构。该仓库包含了常见缓存策略的实现。

缓存类型

来源

LRUCache（最近最少使用）

LRUCache 实现了一个采用最近最少使用（LRU）淘汰策略的缓存。当缓存满时，它首先丢弃最近最少使用的项目。

主要功能

  • 维护一个双向链表以跟踪访问顺序
  • 使用 HashMap 实现 O(1) 的键查找
  • 访问元素时将其移到列表头部
  • 当容量达到上限时从列表末尾移除元素
Time Complexities:
- Get: O(1)
- Put: O(1)

来源

LFUCache（最不常用）

LFUCache 实现了一个采用最不常用（LFU）淘汰策略的缓存。当缓存满时，它首先丢弃最不常用的项目。如果存在平局，则在具有最小频率的项目中移除最近最少使用的项目。

主要功能

  • 跟踪访问频率和最近性
  • 使用 HashMap 实现 O(1) 的键查找
  • 维护频率列表以按访问计数组织项目
  • 访问项目时增加频率计数器
Time Complexities:
- Get: O(1)
- Put: O(1)

来源

MRUCache（最近最常用）

MRUCache 实现了一个采用最近最常用（MRU）淘汰策略的缓存。当缓存满时，它首先丢弃最近最常用的项目，这在旧项目更有可能再次被访问的场景中可能很有用。

主要功能

  • 使用 LinkedHashMap 维护插入顺序
  • 提供 O(1) 的元素访问
  • 当容量达到上限时移除最近访问的项目
Time Complexities:
- Get: O(1)
- Put: O(1)

来源

树实现

树是由节点通过边连接的分层数据结构。该仓库包含了针对不同操作优化的各种树实现。

树层次结构

来源

二叉树

BinaryTree 类实现了一个基本的二叉树，其中每个节点最多有两个子节点。这构成了更专业树结构的基础。

主要功能

  • 基本的插入、搜索和删除操作
  • 多种遍历方法（中序、前序、后序）
  • 支持递归和迭代两种方法

来源

AVL 树

AVLTree 类实现了一个自平衡二叉搜索树，其中任何节点的两个子树的高度差最多为一。

主要功能

  • 插入和删除后的自动平衡
  • 每个节点中存储高度信息
  • 通过旋转操作维持平衡
  • 保证搜索、插入和删除操作的时间复杂度为 O(log n)

来源

红黑二叉搜索树

RedBlackBST 类实现了使用红黑着色规则的自平衡二叉搜索树。

主要功能

  • 基于颜色的平衡（节点为红色或黑色）
  • 在插入和删除过程中维护特定属性
  • 保证搜索、插入和删除操作的时间复杂度为 O(log n)
  • 对于频繁的插入/删除，重新平衡效率高于 AVL 树

来源

线段树

SegmentTree 类实现了用于高效数组范围查询和更新的树形数据结构。

主要功能

  • 支持范围求和、最小值、最大值查询
  • 允许点更新和范围更新
  • 查询和更新的时间复杂度均为 O(log n)
  • 使用懒惰传播实现高效范围更新

来源

Fenwick 树（树状数组）

FenwickTree 类实现了用于高效前缀和计算的空间高效数据结构。

主要功能

  • 比线段树更节省空间
  • 点更新和前缀和查询的时间复杂度均为 O(log n)
  • 基于简单二进制表示的实现
  • 特别适用于累积频率表

来源

Trie树

Trie 类实现了用于存储动态字符串集的树形数据结构，常用于快速前缀搜索。

主要功能

  • 高效的基于前缀的搜索操作
  • 字符串的逐字符存储
  • 操作的时间复杂度为 O(m)，其中 m 是键的长度
  • 用于自动完成和拼写检查等应用

来源

图实现

图是由节点（顶点）通过边连接的数据结构。该仓库包含了各种图的表示和算法。

图算法

来源

图的表示方法

该仓库包含了多种表示图的方式

  1. MatrixGraphs: 使用邻接矩阵表示图，其中二维数组表示顶点之间边的存在和权重。

  2. UndirectedAdjacencyListGraph: 使用邻接列表表示无向图，其中每个顶点维护其相邻顶点的列表。

来源

最短路径算法

  1. DijkstraAlgorithm: 查找带非负边权重的加权图中从源顶点到所有其他顶点的最短路径。

  2. BellmanFord: 计算从单个源顶点到所有其他顶点的最短路径，即使存在负权重边。

  3. FloydWarshall: 查找加权图中所有顶点对之间的最短路径。

  4. JohnsonsAlgorithm: Dijkstra 和 Bellman-Ford 算法的组合，用于在稀疏图中查找所有顶点对之间的最短路径。

来源

最小生成树算法

  1. Kruskal: 通过贪婪地添加不形成循环的最小边来查找最小生成树。

  2. PrimMST: 另一种查找最小生成树的方法，通过从起始顶点生长单个树。

  3. BoruvkaAlgorithm: 一种不同的最小生成树构建方法，同时生长多棵树。

来源

连通分量和循环检测

  1. TarjansAlgorithm: 查找有向图中的强连通分量。

  2. Kosaraju: 另一种查找强连通分量的算法。

  3. ConnectedComponent: 识别无向图中的连通分量。

  4. Cycles: 检测图中的循环。

来源

图着色

  1. WelshPowell: 一种用于图着色的贪婪算法，旨在最小化使用的颜色数量。

来源

HashMap 实现

HashMap 是一种实现关联数组的数据结构，将键映射到值。该仓库包含了多种具有不同冲突解决策略的 HashMap 实现。

HashMap 类型

来源

HashMap

HashMap 类提供了使用单独链表解决冲突的哈希映射的基本实现。

主要功能

  • 使用链表解决冲突（单独链表法）
  • 当负载因子阈值超过时动态调整大小
  • 为基本操作提供 O(1) 的平均时间复杂度

来源

线性探测哈希表

LinearProbingHashMap 类实现了使用线性探测解决冲突的哈希映射。

主要功能

  • 使用开放寻址与线性探测（搜索下一个可用槽位）
  • 比单独链表法更节省内存
  • 聚集风险更高，可能影响性能
  • 当负载因子阈值超过时调整大小

来源

布谷鸟哈希 HashMap

HashMapCuckooHashing 类实现了使用布谷鸟哈希的哈希映射，它提供最坏情况下的常数时间查找。

主要功能

  • 使用两个哈希函数和两个表
  • 插入时，如果发生冲突，现有元素会被“踢出”到其备用位置
  • 如果在插入过程中发生循环，可能需要重新哈希
  • 提供保证 O(1) 的最坏情况查找时间

来源

队列实现

队列是先进先出（FIFO）数据结构，其中元素从尾部插入，从头部移除。

队列类型

来源

循环队列

CircularQueue 类实现了使用循环数组的队列。当队列到达数组末尾时，它会循环回到开头。

主要功能

  • 固定大小实现，空间使用高效
  • 维护头部和尾部指针
  • 入队、出队和窥视操作的时间复杂度为 O(1)
  • 当到达数组末尾时处理循环回绕

来源

链式队列

LinkedQueue 类实现了使用链表的队列，允许动态调整大小。

主要功能

  • 无限容量（仅受可用内存限制）
  • 维护头部和尾部指针，实现 O(1) 的入队和出队操作
  • 无需调整大小或处理循环回绕

来源

优先级队列

PriorityQueues 类实现了一个队列，其中元素具有关联的优先级。优先级较高的元素会在优先级较低的元素之前出队。

主要功能

  • 通常使用堆实现
  • 入队和出队操作的时间复杂度为 O(log n)
  • 窥视操作的时间复杂度为 O(1)
  • 优先级相同的元素按先进先出（FIFO）顺序出队

来源

双端队列（Double-Ended Queue）

Deque 类实现了一个允许在两端进行插入和移除的队列。

主要功能

  • 支持在头部和尾部进行添加/移除操作
  • 比标准队列更灵活
  • 可用于实现堆栈（后进先出 LIFO）和队列（先进先出 FIFO）
  • 通常使用双向链表或循环数组实现

来源

其他专用数据结构

该仓库还包括了几个用于特定用例的专用数据结构。

无冲突复制数据类型 (CRDTs)

CRDTs 是一种数据结构，可以在多个系统之间复制，每个副本可以独立更新而无需协调，并且总能解决不一致性。

已实现的类型

  • GCounter: 只能递增的增长型计数器。
  • PNCounter: 可以递增和递减的计数器。
  • GSet: 只支持添加的增长型集合。
  • TwoPSet: 允许添加和移除，但永远不允许重新添加已移除元素的集合。
  • ORSet: 允许以任意顺序添加和移除的集合。
  • LWWElementSet: 使用时间戳解决冲突操作的集合。

来源

布隆过滤器

BloomFilter 是一种空间高效的概率数据结构，用于测试一个元素是否是集合的成员。可能出现假阳性，但不会出现假阴性。

主要功能

  • 成员查询极其节省空间
  • 添加和包含操作的时间复杂度均为 O(k)，其中 k 是哈希函数的数量
  • 一旦添加，无法移除元素
  • 用于缓存、拼写检查和检测重复内容等应用

来源

不相交集并

DisjointSetUnion 实现了一种数据结构，用于跟踪一组被划分为不相交（不重叠）子集的元素。

主要功能

  • 支持“并集”操作以合并两个集合
  • 支持“查找”操作以确定元素属于哪个集合
  • 通过路径压缩和按秩合并，操作的时间复杂度接近常数
  • 用于 Kruskal 算法等查找最小生成树的算法

来源

动态数组

DynamicArray 类实现了一个可变大小的数组，可根据需要增长。

主要功能

  • 与标准数组接口类似，但具有动态大小调整功能
  • 追加操作的均摊时间复杂度为 O(1)
  • 随机访问的时间复杂度为 O(1)
  • 平衡了灵活性和效率

来源

结论

本页面概述了 TheAlgorithms/Java 仓库中可用的众多数据结构实现。每个实现都旨在演示不同数据结构的属性、操作和权衡，使其对学习和参考都具有价值。

有关操作这些数据结构的算法实现，请参阅“算法”部分。

来源