Data structure cheat sheet: Difference between revisions
Jump to navigation
Jump to search
Hoppinglife (talk | contribs) |
Hoppinglife (talk | contribs) |
||
| (13 intermediate revisions by the same user not shown) | |||
| Line 25: | Line 25: | ||
=== Median and order statistics === | === Median and order statistics === | ||
Selecting min/max from the array takes linear time, and selecting the general <math>k^{th}</math> element takes a expected <math>\Theta(n)</math> time using a method similar to quicksort. | |||
== Tree-based Structures == | == Tree-based Structures == | ||
=== Binary Tree === | === Binary Tree === | ||
==== Property ==== | ==== Property ==== | ||
* A full n-level binary tree have <math>2^n - 1</math> elements. | |||
* A n-node binary tree have <math>\lceil log n \rceil + 1 </math> levels. | |||
==== Storage ==== | |||
==== Traversal ==== | ==== Traversal ==== | ||
General traversal of binary trees all takes <math>O(n)</math> time, except for the root node, exactly two times of the search routine was called for each node. | |||
For Binary Search Trees, Min/Max is easy - just follow the left/right link. Getting successor/predecessor is tricker: the next element of x is either a) the minimum element of the right subtree, or b) the lowest ancestor of x whose left child is also the ancestor of x. | |||
==== Insertion and Deletion ==== | |||
Insertion is relatively simple, just follows the search procedure until you find an empty node. | |||
Deletion is more complicated: if the target <math>z</math> has two children, we find the successor of <math>z</math>, if it is the right child of <math>z</math>, it can be replaced by y, otherwise, we first replace y by its right child, then replace z using y. | |||
=== Heap === | === Heap === | ||
| Line 92: | Line 109: | ||
Fundamentally, the representation of a graph is always equivalent to an adjacent matrix. The most usual methods are uncompressed matrix, adjacent list, and compressed matrix. | Fundamentally, the representation of a graph is always equivalent to an adjacent matrix. The most usual methods are uncompressed matrix, adjacent list, and compressed matrix. | ||
=== Traverse === | === Traverse === | ||
=== | * BFS is the simplest traverse one can conduct on a graph. Useful to do the basic shortest path discoveries. | ||
=== | * DFS is useful for establishing strongly connected components. It can also be used to classify edges in the graph (tree edge, back, forward, cross). | ||
=== Topological sort and Strongly Connected Components === | |||
* As each vertex is finished, insert it into the front of a linked list. | |||
* For directional graphs, its strongly connected graph can be computed in the following way: 1) do a DFS to establish topological order, 2) do the DFS on the transposed graph using the order in reverse order of its finishing time. | |||
=== Minimum Spanning Trees === | |||
* Kruskal: add the lowest edge that connected different components. <math>O(E lg V)</math> | |||
* Prim: find the light edge between the sites. <math>O(E lg V)</math> | |||
=== Shortest Paths === | |||
* Bellman-Ford: relax each edge V times, O(VE). | |||
* DAG can be done in O(V+E) time, by looking at it in topological order. | |||
* Dijkstra: relax all the edges of the newly visited node. O(V^2) | |||
== Dynamic Programming == | == Dynamic Programming == | ||
| Line 101: | Line 128: | ||
== Searching == | == Searching == | ||
=== Depth-first search / backtracking === | |||
=== Breath-first search === | |||
== Mathematical Problems == | |||
=== Permutations and Combinations === | |||
==== Generate next lexicographic permutation ==== | |||
* find the longest non-increasing suffix: | |||
<pre>67[1]5432</pre> | |||
* find the last element that is larger than the previous one: | |||
<pre>67[1]543[2]</pre> | |||
* swap | |||
<pre>67[2]543[1]</pre> | |||
* reverse the tail: | |||
<pre>672[1345]</pre> | |||
==== Generate the k-th permutation of N ==== | |||
The idea is to generate the permutation one element by one element: | |||
we can determine the first element of the permutation by comparing k with N, | |||
then repeat this procedure. | |||
==== Generate permutations with the duplications ==== | |||
This can be done with a simple backtracking search. | |||
==== Heap's algorithm ==== | |||