请稍侯

Keith Schwarz算法实现

04 July 2016

Keith Schwarz是一个斯坦福大学计算机科学系的讲师，他在自己的 主页上实现了各种各样有意思的算法和数据结果。

算法列表

算法 链接 语言 简介
Binomial Heap link C++ An implementation of a binomial heap data structure for use as a priority queue.
Bounded Priority Queue link C++ An implementation of a priority queue with a fixed upper limit to its size..
Matrix link C++ A collection of classes for manipulating matrices.
VList link Java An implementation of the List abstraction backed by a VList.
Function Wrapper link C++ A C++ wrapper class around unary functions.
String link C++ An implementation of a string abstraction that uses the small string optimization.
nstream link C++ An stream class that sends and receives data over a network.
Snake link C++ An implementation of the game Snake with a rudimentary AI.
Mergesort link C++ An implementation of the mergesort algorithm.
Next Permutation link C++ An implementation of the next_permutation STL algorithm.
Interval Heap link Java An implementation of a double-ended priority queue using an interval heap.
Linear-Time Selection link C++ A deterministic, linear-time selection algorithm using the median-of-medians algorithm.
Heapsort link C++ An implementation of the heapsort algorithm.
Union-Find link Java An implementation of a disjoint-set data structure using a disjoint set forest.
Radix Sort link C++ An implementation of the radix sort algorithm.
Rational link C++ A data structure representing a rational number.
DPLL link Haskell An implementation of the DPLL algorithm for solving CNF-SAT.
Smoothsort link C++ An implementation of the smoothsort algorithm, an adaptive heapsort variant.
Extendible Array link Java A dynamic array class with O(1) worst-case runtime lookup and append.
In-Place Merge link C++ An implementation of a merge algorithm that runs in-place.
Random Shuffle link C++ An algorithm for generating a random permutation of a set of elements.
Random Sample link C++ An O(n) time, O(1) space algorithm for randomly choosing k elements out of a stream with uniform probability.
Natural Mergesort link C++ An implementation of natural mergesort, an adaptive variant of mergesort.
Interpolation Search link C++ An implementation of the interpolation search algorithm.
Introsort link C++ An implementation of the introsort algorithm, a fast hybrid of quicksort, heapsort, and insertion sort.
Hashed Array Tree link Java An implementation of a dynamic array backed by a hashed array tree.
Recurrence Solver link C++ A fast algorithm for generating terms of a sequence defined by a linear recurrence relation.
Fibonacci Heap link Java An implementation of a priority queue backed by a Fibonacci heap.
Dijkstra’s Algorithm link Java An implementation of Dijkstra’s algorithm for single-source shortest paths.
Prim’s Algorithm link Java An implementation of Prim’s algorithm for computing minimum spanning trees.
Kruskal’s Algorithm link Java An implementation of Kruskal’s algorithm for computing minimum spanning trees.
Majority Element link C++ A fast, linear-time algorithm for finding the majority element of a data set.
Haar Transform link C++ A set of functions to decompose a sequence of values into a sum of Haar wavelets.
Argmax link C++ A pair of functions to compute the arg min or max of a function on some range.
Derivative link C++ A function object that approximates the derivative of a function.
Levenshtein Distance link C++ An algorithm for computing the Levenshtein distance between two sequences.
Skiplist link C++ An implementation of a skip list, a randomized data structure for maintaining a sorted collection.
van Emde Boas Tree link C++ An implementation of a sorted associative array backed by a van Emde Boas tree.
Cuckoo HashMap link Java An implementation of a hash table using cuckoo hashing.
Needleman-Wunsch Algorithm link C++ An implementation of the Needleman-Wunsch algorithm for optimal string alignment.
Treap link C++ An implementation of a sorted associative array backed by a treap.
Floyd-Warshall Algorithm link Java An implementation of the Floyd-Warshall algorithm for all-pairs shortest paths in a graph.
Power Iteration link C++ An implementation of the power iteration algorithm for finding dominant eigenvectors.
Edmonds’s Matching Algorithm link Java An implementation of Edmonds’s matching algorithm for finding maximum matchings in undirected graphs.
Kosaraju’s Algorithm link Java An implementation of Kosaraju’s algorithm algorithm for finding strongly connected components of a directed graph.
2-SAT link Java A linear-time algorithm for solving 2-SAT.
Bellman-Ford Algorithm link Java An implementation of the Bellman-Ford algorithm for single-source shortest paths.
Topological Sort link Java An algorithm for computing a topological sort of a directed acyclic graph.
Graham Scan link C++ An implementation of the Graham scan for finding convex hulls in 2D space.
Bipartite Testing link Java A linear-time algorithm for checking whether a directed graph is bipartite.
Johnson’s Algorithm link Java An implementation of Johnson’s algorithm for all-pairs shortest paths.
Strassen Algorithm link C++ An implementation of the Strassen algorithm for fast matrix multiplication.
Cartesian Tree Sort link C++ An implementation of Cartesian tree sort, an adaptive, out-of-place heapsort variant.
Ford-Fulkerson Algorithm link Java An implementation of the Ford-Fulkerson maximum-flow algorithm.
Scaling Ford-Fulkerson link Java An modification of the Ford-Fulkerson maximum-flow algorithm that uses scaling to achieve polynomial time..
Splay Tree link C++ An implementation of a sorted associative array backed by a splay tree.
Ternary Search Tree link C++ An implementation of a sorted set of strings backed by a ternary search tree.
Ring Buffer link Java An implementation of a FIFO queue using a ring buffer.
AVL Tree link C++ A sorted associative container backed by an AVL tree.
Rabin-Karp Algorithm link C++ An implementation of the Rabin-Karp algorithm for string matching.
RPN Evaluator link C++ / strain A library to tokenize and evaluate simple arithmetic expressions in reverse Polish notation.
Shunting-Yard Algorithm link C++ / strain An implementation of Dijkstra’s shunting-yard algorithm for converting infix expressions to reverse-Polish notation.
Skew Binomial Heap link C++ An implementation of a priority queue backed by a skew binomial heap.
2/3 Heap link C++ An implementation of a priority queue whose branching factor alternates at different levels to maximize performance.
Zeckendorf Logarithm link C++ An algorithm based on Zeckendorf representations that efficiently computes logarithms.
Factoradic Permutations link C++ A set of algorithms for generating permutations using the factoradic number system.
Binary Cyclic Subsets link C++ A set of algorithms for generating subsets in lexicographical order using binary numbers and cyclic shifts.
Fibonacci Iterator link C++ An STL-style iterator for iterating over the Fibonacci numbers.
Fibonacci Search link C++ An implementation of the Fibonacci search algorithm.
Euclid’s Algorithm link Haskell An implementation of Euclid’s algorithm and applications to continued fractions and the extended Euclidean algorithm.
Find Duplicate link Python An algorithm to find a repeated element in an array using Floyd’s cycle-finding algorithm.
Permutation Generator link Python A generator for producing all permutations of a list of elements.
Matrix Find link Python A solution to the classic interview question of searching a sorted matrix for a particular value.
Binary GCD link Scheme An implementation of the binary GCD algorithm for computing greatest common divisors of nonnegative integers.
Knuth-Morris-Pratt Algorithm link Python An implementation of the Knuth-Morris-Pratt algorithm for fast string matching.
Kadane’s Algorithm link C++ An implementation of Kadane’s algorithm for solving the maximum-weight subarray problem.
Karatsuba’s Algorithm link Python An implementation of Karatsuba’s algorithm for fast integer multiplication.
Min-Stack link C++ An implementation of a LIFO stack that supports O(1) push, pop, and find-minimum.
Random Bag link Python A data structure that supports insertion and removal of a uniformly-random element.
Min-Queue link C++ An implementation of a FIFO queue that supports O(1) push, pop, and find-minimum.
Lights-Out Solver link C++ A solver for the game Lights Out using Gaussian elimination over GF(2).
Maximum Single-Sell Profit link Python Four algorithms for the maximum single-sell profit problem, each showing off a different algorithmic technique.
Generalized Kadane’s Algorithm link C++ A generalization of Kadane’s algorithm for solving the maximum subarray problem subject to a length restriction.
Longest Range link Java An algorithm for solving the longest contiguous range problem.
Egyptian Fractions link Python An implementation of the greedy algorithm for finding Egyptian fractions.
LL(1) Parser Generator link Java An LL(1) parser generator.
LR(0) Parser Generator link Java An LR(0) parser generator.
Word Ladders link JavaScript A program for finding word ladders between two words.
Alias Method link Java An implementation of the alias method for sampling from a discrete probability distribution.
Binary Quicksort link C++ An implementation of the binary quicksort (binary MSD radix sort) algorithm.
Ternary Sierpinski Triangle link JavaScript An algorithm for drawing the Sierpinksi triangle using ternary numbers.
In-Place Tree Delete link C++ An algorithm for deleting all of the nodes of a binary tree using O(1) auxiliary storage space.
Random Access List link Haskell A purely functional, persistent random-access sequence backed by a random access list.
BST LCA link Haskell A function for finding the lowest common ancestor of two nodes in a binary search tree.
Matrix Fill link Java An algorithm for solving the matrix fill problem, an interview problem from Microsoft.