# Graphs

Graphs are an integral part of computer science. Mastering them is necessary to become an accomplished software developer. Here is the data structure analysis of graphs:

Node/Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
---|---|---|---|---|---|---|

Adjacency List | O(|V|+|E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) |

Incidence List | O(|V|+|E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) |

Adjacency Matrix | O(|V|^2) | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(1) |

Incidence Matrix | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|E|) |

# Heaps

Storing information in a way that is quick to retrieve, add, and search on, is a very important technique to master. Here is what you need to know about heap data structures:

Heaps | Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge |
---|---|---|---|---|---|---|---|

Sorted Linked List | - | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) |

Unsorted Linked List | - | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) |

Binary Heap | O(n) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(m+n) |

Binomial Heap | - | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |

Fibonacci Heap | - | O(1) | O(log(n))* | O(1)* | O(1) | O(log(n))* | O(1) |