Data structure cheat sheet: Difference between revisions
Jump to navigation
Jump to search
Hoppinglife (talk | contribs) |
Hoppinglife (talk | contribs) |
||
| (14 intermediate revisions by the same user not shown) | |||
| Line 10: | Line 10: | ||
=== Arrays === | === Arrays === | ||
== Sorting == | == Sorting and Ordering == | ||
=== Simple Sort === | === Simple Sort === | ||
| Line 18: | Line 18: | ||
=== Quick Sort === | === Quick Sort === | ||
The core of the quicksort is dividing the sorting array into half and repeat this operation. The dividing procedure is called ''partition'', and there are two typical implementations of it: Lomuto and Hoare partition. The | The core of the quicksort is dividing the sorting array into half and repeat this operation. The dividing procedure is called ''partition'', and there are two typical implementations of it: Lomuto and Hoare partition. The Lomuto partition process the elements one by one, and swap the elements smaller than the pivot to the left side. Hoare partition goes through the arrays on both ends, swap pairs on the wrong side, and end the progress when the two scan meets. | ||
Quicksort on average takes <math>\Theta(n lg n)</math> time. Worse case it can cause <math>\Theta(n^2)</math>. There are a number of algorithms based on the idea of doing partitions and processing either or both sides of it. If only one side of it is processed, it uses O(n) time. | Quicksort on average takes <math>\Theta(n lg n)</math> time. Worse case it can cause <math>\Theta(n^2)</math>. There are a number of algorithms based on the idea of doing partitions and processing either or both sides of it. If only one side of it is processed, it uses O(n) time. | ||
=== Merge Sort === | === Merge Sort === | ||
=== 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 90: | 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 99: | 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 ==== | |||