Classic Algorithms and Data Structures implemented in Java

Algorithms

Algorithm	Worst-case time complexity	Average-case time complexity	Best-case time complexity	Auxiliary space complexity
Insertion Sort	Θ(n^2)	Θ(n^2)	O(n)	-
BubbleSort	O(n^2)	O(n^2)	O(n)	-
MergeSort	Θ(nlogn)	Θ(nlogn)	Θ(nlogn)	-
HeapSort	Θ(nlogn)	-	-	-
QuickSort	Θ(n^2)	Θ(nlogn)	Θ(nlogn)	-
CountingSort	Θ(k + n)	Θ(k + n)	Θ(n)	Θ(n)
RadixSort	Θ(d(k + n))	Θ(d(k + n))	Θ(n)	-
Floyd-Warshall	Θ(V^3)	Θ(V^3)	Θ(V^3)	Θ(V^2)
Kruskal	O(|E|log|V|)	-	-	-
Prim	O(|E| + |V|log|V|	-	-	-
Bellman–Ford	Θ(|E||V|)	-	-	Θ(V)
Dijkstra	O(|E| + |V|log|V|)	-	-	-
Maximum SubArray	Θ(n)	Θ(n)	Θ(n)	Θ(1)
Knuth-Morris-Pratt	Θ(n + m)	Θ(n)	Θ(n)	Θ(n)
Rabin-Karp	Θ((n - m + 1)m)	Θ(n)	Θ(n)	-
Greatest common divisor (GCD)	-	-	-	-
Binary Search	O(nlogn)	O(nlogn)	O(1)	Θ(1)
Breadth First Search (BFS)	O(|E|+|V|)	O(|E|+|V|)	-	-
Depth First Search (DFS)	O(|E|+|V|)	O(|E|+|V|)	-	-
Topological Sort (DFS)	O(|E|+|V|)	O(|E|+|V|)	-	-
Longest Increasing Subsequence (LIS)	Θ(n^2)	-	-	Θ(n)
Longest Common Subsequence (LCS)	Θ(n^2)	-	-	Θ(n^2)

Data Structures

Data Structure	Methods
Max Heap	max() - Θ(1), extractMax() - O(nlogn), increaseKey() - O(logn), insert() - O(logn), heapify() - O(logn), heapsort() - O(nlogn)
Min Heap	min() - Θ(1), extractMin() - O(nlogn), insert() - O(logn), heapify() - O(logn), heapsort() - O(nlogn)
MinMax Heap	min() - Θ(1), max() - Θ(1), extractMin() - O(nlogn), extractMax() - O(nlogn), insert() - O(logn), heapify() - O(logn)
Disjoint Set	makeSet() - Θ(1), findSet() - Θ(1), union() - Θ(1)
Trie	insert() - O(|s|), search() - O(|s|), searchPrefix() - O(|s|), remove() - O(|s|), size() - O(1)
Stack	push() - Θ(1), pop() - Θ(1), empty() - Θ(1), size() - Θ(1), peek() - Θ(1)
Queue	enqueue() - Θ(1), dequeue() - Θ(1), empty() - Θ(1), size() - Θ(1)
Binary Search Tree	insert() - O(n), search() - O(n), delete() - O(n), contains() - O(n), minimum() - O(n), maximum() - O(n), size() - Θ(1), successor() - O(logn), predecessor() - O(logn), preOrderVisit() - O(n), inOrderVisit() - O(n), postOrderVisit() - O(n)
Double Linked List	insertFront() - Θ(1), removeFront() - Θ(1), insertBack() - Θ(1), removeBack() - Θ(1), head() - Θ(1), size() - Θ(1), search() - Θ(n), remove() - Θ(n)
Linked List	insertFront() - Θ(1), removeFront() - Θ(1), head() - Θ(1), size() - Θ(1), search() - Θ(n), remove() - Θ(n)
Skip List	insert() - Θ(logn), remove() - Θ(logn), search() - O(logn), size() - Θ(1)
Graph	buildAdjacencyMatrix() - Θ(|V|^2), buildAdjacencyList() - Θ(|V| + |E|), addEdge() - Θ(1)
Red-Black Tree	insert() - O(logn), search() - O(logn), delete() - O(logn), minimum() - O(logn), maximum() - O(logn), successor() - O(logn), predecessor() - O(logn)
Interval Tree	insert() - O(logn), search() - O(logn), find() - O(logn), findAll() - O(n), delete() - O(logn), minimum() - O(logn), maximum() - O(logn), successor() - O(logn), predecessor() - O(logn)
Segment Tree	build() - O(n), update() - O(logn), search() - O(logn)
AVL Tree	insert() - O(logn), search() - O(logn), delete() - O(logn), minimum() - O(logn), maximum() - O(logn), successor() - O(logn)
B-Tree	insert() - O(th), search() - O(th), delete() - O(th), successor() - O(th), predecessor() - O(th)
QuadTree	insert() - O(logn), search() - O(logn), delete() - O(logn), size() - Θ(1)
Fibonacci Heap	insert() - O(1), minimum() - O(1), extractMin() - O(logn), decreaseKey() - O(1), delete() - O(logn)
Merkle Tree	build() - O(n), verify() - O(logn), getProofPath() - O(logn)
Bloom Filter	search() - O(k), insert() - O(k)

---

Add to your build

To add a dependency using Gradle, use the following:

implementation 'com.alexprut:algo:v0.4.0'

To add a dependency using Gradle Kotlin DSL:

implementation("com.alexprut:algo:v0.4.0")

To add a dependency using Maven:

<dependency>
  <groupId>com.alexprut</groupId>
  <artifactId>algo</artifactId>
  <version>v0.4.0</version>
</dependency>

Requirements

• Gradle 8
• Java 11

Build

./gradlew clean build

Test

./gradlew test

Formatting style

./gradlew goJF

./gradlew verGJF

Generate Changelog

git-chglog v1.0.0..v2.0.0

License

Licensed under MIT.