|
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 |
|
━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━ |
