Algorithms and Data Structures implemented in Java
This is a collection of algorithms and data structures which I've implement over the years in my academic and professional life. The code isn't overly-optimized but is written to be correct and readable. The algorithms and data structures are well tested and, unless noted, are believe to be 100% correct.
- Created by Justin Wetherell
- For questions use: http://groups.google.com/forum/#!forum/java-algorithms-implementation
- Google: http://code.google.com/p/java-algorithms-implementation
- Github: http://github.com/phishman3579/java-algorithms-implementation
- LinkedIn: http://www.linkedin.com/in/phishman3579
- E-mail: phishman3579@gmail.com
- Twitter: http://twitter.com/phishman3579
- AVL Tree
- B-Tree
- Binary Heap [backed by an array or a tree]
- Binary Search Tree
- Compact Suffix Trie [backed by a Patricia Trie]
- Disjoint Set
- Fenwick Tree [Binary Indexed Tree (BIT)]
- Graph
- Undirected
- Directed (Digraph)
- Hash Array Mapped Trie (HAMT)
- Hash Map (associative array)
- Interval Tree
- Implicit Key Treap
- KD Tree (k-dimensional tree or k-d tree)
- List [backed by an array or a linked list]
- Matrix
- Patricia Trie
- Quad-Tree (Point-Region or MX-CIF)
- Queue [backed by an array or a linked list]
- Radix Trie (associative array) [backed by a Patricia Trie]
- Red-Black Tree
- Segment Tree
- Skip List
- Splay Tree
- Stack [backed by an array or a linked list]
- Suffix Tree (Ukkonen's algorithm)
- Suffix Trie [backed by a Trie]
- Treap
- Tree Map (associative array) [backed by an AVL Tree]
- Trie
- Trie Map (associative array) [backed by a Trie]
- Distance
- chebyshev
- euclidean
- Division
- using a loop
- using recursion
- using shifts and multiplication
- using only shifts
- using logarithm
- Multiplication
- using a loop
- using recursion
- using only shifts
- using logarithms
- using FFT
- Primes
- is prime
- prime factorization
- sieve of eratosthenes
- co-primes (relatively prime, mutually prime)
- greatest common divisor
- using Euclid's algorithm
- using recursion
- Permutations
- strings
- numbers
- Modular arithmetic
- add
- subtract
- multiply
- divide
- power
- Integers
- to binary String
- using divide and modulus
- using right shift and modulus
- using BigDecimal
- using divide and double
- is a power of 2
- using a loop
- using recursion
- using logarithm
- using bits
- to English (e.g. 1 would return "one")
- to binary String
- Longs
- to binary String
- using divide and modulus
- using right shift and modulus
- using BigDecimal
- to binary String
- Complex
- addition
- subtraction
- multiplication
- absolute value
- polar value
- Find shortest path(s) in a Graph from a starting Vertex
- Dijkstra's algorithm (non-negative weight graphs)
- Bellman-Ford algorithm (negative and positive weight graphs)
- Find minimum spanning tree
- Prim's (undirected graphs)
- Kruskal's (undirected graphs)
- Find all pairs shortest path
- Johnsons's algorithm (negative and positive weight graphs)
- Floyd-Warshall (negative and positive weight graphs)
- Cycle detection
- Depth first search while keeping track of visited Verticies
- Topological sort
- A* path finding algorithm
- Maximum flow
- Push-Relabel
- Get index of value in array
- Linear
- Quickselect
- Binary [sorted array input only]
- Lower bound [sorted array input only]
- Upper bound [sorted array input only]
- Optimized binary (binary until a threashold then linear) [sorted array input only]
- Interpolation [sorted array input only]
- Find longest common subsequence (dynamic programming)
- Find longest increasing subsequence (dynamic programming)
- Find number of times a subsequence occurs in a sequence (dynamic programming)
- Find i-th element in a Fibonacci sequence
- using a loop
- using recursion
- using matrix multiplication
- using Binet's formula
- Find total of all elements in a sequence
- using a loop
- using Triangular numbers
- American Flag Sort
- Bubble Sort
- Counting Sort (Integers only)
- Heap Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Radix Sort (Integers only)
- Shell's Sort
- Reverse characters in a string
- using additional storage (a String or StringBuilder)
- using in-place swaps
- using in-place XOR
- Reverse words in a string
- using char swaps and additional storage (a StringBuilder)
- using StringTokenizer and additional (a String)
- using split() method and additional storage (a StringBuilder and String[])
- using in-place swaps
- Is Palindrome
- using additional storage (a StringBuilder)
- using in-place symetric element compares
- Subsets of characters in a String
- Edit (Levenshtein) Distance of two Strings
- KMP (Knuth–Morris–Pratt) Algorithm - Length of maximal prefix-suffix for each prefix
- String rotations
- Findin lexicographically minimal string rotation
- Findin lexicographically maximal string rotation