- Heap is array data structure.
- heap isperfectly_balanced, everything is stored as contiguous memory in array.
- priority_queue andheap mean the same thing.
- Dijkstras_algorithm ,prims_algorithm ,huffman_coding,minimum_spanning_tree all useheap orpriority_queue
- Application:
- cpu_scheduling
- Queue where priority is involved e.g. scheduling tasks in azure devops by priority
- Example: Choose n items given the price of items and money you have.
- Question: Elevator programming, since different floors have different priority, will we use heap here and since heap and priority queue is same? Ans. Use min heap. But we will need another data structure as well.
Graph
- Applications:
- Routers
- Social media networks
- Computer networks
- graph_edge andgraph_node orgraph_vertices
- adjacency_matrix vsadjacency_list
- Removing an edge in social media network is better withadjacency_matrix , unfriend someone from network.
- adjacency_matrix takes a lot of space so space wastage.
- Adding a vertex is costly withadjacency_matrix
- BFS, DFS, Prims algo are difficult withadjacency_matrix
- Time complexity changes based on above selection.
- Question: Euro trip, I start with one country and want to take trip to adjacent countries only, is graph the correct DS here. And is there any particular algorithm that fits in here? Ans. Adj list and BFS. In BFS we go in circles.
- adjacency_list can also be an array of array if only integers are involved.
- Locality of items,cache_friendly
- Ford_Fulkerson algo is example where you preferadjacency_matrix .
- Sandeep_Jain repeated my question quoting, ‘Like a gentlemen asked’ :D
- visited_array will be used for DFS.
- Applications of BFS:
- Application of DFS:
- topological_sorting is important, makewhile utility used to use it.Topological Sort
