Created
August 26, 2016 02:32
-
-
Save reinh/148f7e262f9c5599cb5038e9fd9f8ccf to your computer and use it in GitHub Desktop.
Revisions
-
reinh renamed this gist
Aug 26, 2016 . 1 changed file with 0 additions and 0 deletions.There are no files selected for viewing
File renamed without changes. -
Aug 26, 2016 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,63 @@ Priority Queues ═══════════════ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ INSERT DEL-MIN MIN DEC-KEY DELETE MERGE binary log n log n 1 log n log n n binomial 1 log n 1 log n log n log n Fibonacci 1 log n† 1 1† log n† log n Pairing 1† log n† 1† 1† log n† 1† Brodal-Okasaki 1 log n 1 1 log n 1 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ † amortized Graph Processing ════════════════ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ PROBLEM │ ALGORITHM TIME SPACE path │ DFS E + V V cycle │ DFS E + V V directed cycle │ DFS E + V V topological sort │ DFS E + V V bipartiteness / odd cycle │ DFS E + V V connected components │ DFS E + V V strong components │ Kosaraju–Sharir E + V V Eulerian cycle │ DFS E + V E + V directed Eulerian cycle │ DFS E + V V transitive closure │ DFS V (E + V) V² minimum spanning tree │ Kruskal E log E E + V minimum spanning tree │ Prim E log V V minimum spanning tree │ Boruvka E log V V shortest paths (unit weights) │ BFS E + V V shortest paths (nonnegative weights) │ Dijkstra E log V V shortest paths (negative weights) │ Bellman–Ford V (V + E) V all-pairs shortest paths │ Floyd–Warshall V³ V² maxflow–mincut │ Ford–Fulkerson E V (E + V) V bipartite matching │ Hopcroft–Karp V √(E + V) V ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Common Data Structures and Operations ═════════════════════════════════════ ━━━━━━━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┯━━━━━━━━━ DATA STRUCTURE │ TIME │ │ SPACE │ AVERAGE │ WORST │ WORST │ ACCESS SEARCH INSERTION │ DELETION ACCESS SEARCH INSERTION DELETION │ Array │ 1 n n │ n 1 n n n │ n Stack │ n n 1 │ 1 n n 1 1 │ n Queue │ n n 1 │ 1 n n 1 1 │ n Singly-Linked List │ n n 1 │ 1 n n 1 1 │ n Doubly-Linked List │ n n 1 │ 1 n n 1 1 │ n Skip List │ log n log n log n │ log n n n n n │ n log n Hash Table │ N/A 1 1 │ 1 N/A n n n │ n Binary Search Tree │ log n log n log n │ log n n n n n │ n Cartesian Tree │ N/A log n log n │ log n N/A n n n │ n B-Tree │ log n log n log n │ log n log n log n log n log n │ n Red-Black Tree │ log n log n log n │ log n log n log n log n log n │ n Splay Tree │ N/A log n log n │ log n N/A log n log n log n │ n AVL Tree │ log n log n log n │ log n log n log n log n log n │ n KD Tree │ log n log n log n │ log n n n n n │ n ━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━ This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,68 @@ #+OPTIONS: ':nil *:t -:t ::t <:t H:3 \n:nil ^:t arch:headline author:nil c:nil #+OPTIONS: creator:nil d:(not "LOGBOOK") date:nil e:t email:nil f:t inline:t #+OPTIONS: num:nil p:nil pri:nil prop:nil stat:t tags:t tasks:t tex:t timestamp:t #+OPTIONS: title:nil toc:nil todo:t |:t #+TITLE: Data Structures Cheat Sheet #+DATE: <2016-08-18 Thu> #+AUTHOR: Rein Henrichs #+EMAIL: [email protected] #+LANGUAGE: en #+CREATOR: Emacs 25.1.1 (Org mode 8.3.5) * Priority Queues | | INSERT | DEL-MIN | MIN | DEC-KEY | DELETE | MERGE | | / | | | | | | | | binary | log n | log n | 1 | log n | log n | n | | binomial | 1 | log n | 1 | log n | log n | log n | | Fibonacci | 1 | log n† | 1 | 1† | log n† | log n | | Pairing | 1† | log n† | 1† | 1† | log n† | 1† | | Brodal-Okasaki | 1 | log n | 1 | 1 | log n | 1 | | | <l> | | <l> | | | | † amortized * Graph Processing | PROBLEM | ALGORITHM | TIME | SPACE | | / | < | | | | path | DFS | E + V | V | | cycle | DFS | E + V | V | | directed cycle | DFS | E + V | V | | topological sort | DFS | E + V | V | | bipartiteness / odd cycle | DFS | E + V | V | | connected components | DFS | E + V | V | | strong components | Kosaraju–Sharir | E + V | V | | Eulerian cycle | DFS | E + V | E + V | | directed Eulerian cycle | DFS | E + V | V | | transitive closure | DFS | V (E + V) | V² | | minimum spanning tree | Kruskal | E log E | E + V | | minimum spanning tree | Prim | E log V | V | | minimum spanning tree | Boruvka | E log V | V | | shortest paths (unit weights) | BFS | E + V | V | | shortest paths (nonnegative weights) | Dijkstra | E log V | V | | shortest paths (negative weights) | Bellman–Ford | V (V + E) | V | | all-pairs shortest paths | Floyd–Warshall | V³ | V² | | maxflow–mincut | Ford–Fulkerson | E V (E + V) | V | | bipartite matching | Hopcroft–Karp | V √(E + V) | V | * Common Data Structures and Operations | DATA STRUCTURE | TIME | | | | | | | | SPACE | | | AVERAGE | | | WORST | | | | | WORST | | | ACCESS | SEARCH | INSERTION | DELETION | ACCESS | SEARCH | INSERTION | DELETION | | | / | < | | | < | | | | | < | | Array | 1 | n | n | n | 1 | n | n | n | n | | Stack | n | n | 1 | 1 | n | n | 1 | 1 | n | | Queue | n | n | 1 | 1 | n | n | 1 | 1 | n | | Singly-Linked List | n | n | 1 | 1 | n | n | 1 | 1 | n | | Doubly-Linked List | n | n | 1 | 1 | n | n | 1 | 1 | n | | Skip List | log n | log n | log n | log n | n | n | n | n | n log n | | Hash Table | N/A | 1 | 1 | 1 | N/A | n | n | n | n | | Binary Search Tree | log n | log n | log n | log n | n | n | n | n | n | | Cartesian Tree | N/A | log n | log n | log n | N/A | n | n | n | n | | B-Tree | log n | log n | log n | log n | log n | log n | log n | log n | n | | Red-Black Tree | log n | log n | log n | log n | log n | log n | log n | log n | n | | Splay Tree | N/A | log n | log n | log n | N/A | log n | log n | log n | n | | AVL Tree | log n | log n | log n | log n | log n | log n | log n | log n | n | | KD Tree | log n | log n | log n | log n | n | n | n | n | n |