Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━

Data Structures Cheat Sheet

Priority Queues

INSERTDEL-MINMINDEC-KEYDELETEMERGE
/
binarylog nlog n1log nlog nn
binomial1log n1log nlog nlog n
Fibonacci1log n†11†log n†log n
Pairing1†log n†1†1†log n†1†
Brodal-Okasaki1log n11log n1
<l><l>

† amortized

Graph Processing

PROBLEMALGORITHMTIMESPACE
/<
pathDFSE + VV
cycleDFSE + VV
directed cycleDFSE + VV
topological sortDFSE + VV
bipartiteness / odd cycleDFSE + VV
connected componentsDFSE + VV
strong componentsKosaraju–SharirE + VV
Eulerian cycleDFSE + VE + V
directed Eulerian cycleDFSE + VV
transitive closureDFSV (E + V)
minimum spanning treeKruskalE log EE + V
minimum spanning treePrimE log VV
minimum spanning treeBoruvkaE log VV
shortest paths (unit weights)BFSE + VV
shortest paths (nonnegative weights)DijkstraE log VV
shortest paths (negative weights)Bellman–FordV (V + E)V
all-pairs shortest pathsFloyd–Warshall
maxflow–mincutFord–FulkersonE V (E + V)V
bipartite matchingHopcroft–KarpV √(E + V)V

Common Data Structures and Operations

DATA STRUCTURETIMESPACE
AVERAGEWORSTWORST
ACCESSSEARCHINSERTIONDELETIONACCESSSEARCHINSERTIONDELETION
/<<<
Array1nnn1nnnn
Stacknn11nn11n
Queuenn11nn11n
Singly-Linked Listnn11nn11n
Doubly-Linked Listnn11nn11n
Skip Listlog nlog nlog nlog nnnnnn log n
Hash TableN/A111N/Annnn
Binary Search Treelog nlog nlog nlog nnnnnn
Cartesian TreeN/Alog nlog nlog nN/Annnn
B-Treelog nlog nlog nlog nlog nlog nlog nlog nn
Red-Black Treelog nlog nlog nlog nlog nlog nlog nlog nn
Splay TreeN/Alog nlog nlog nN/Alog nlog nlog nn
AVL Treelog nlog nlog nlog nlog nlog nlog nlog nn
KD Treelog nlog nlog nlog nnnnnn
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment