c++

Topics- 1. check given array is heap 2. convert max to min heap 3. Kth smallest element 4. Kth largest element 5. Top K freq elements Extras- 1. Quick Sort 2. Bucket Sort 3. Heap Sort ------------------------------------------------------------------------------------------------------------------------- Heaps implementation using arrays-                         Max heap                                                                             Min Heap      ------------------------------------------------------------ Heapify Algo : to place an element into its correct position in a binary heap  -----------------------------------------------------------------------------------------------------...

Note- 1. complete BT has all levels filled except last level & nodes are filled from left to right 2. a complete BT with last level being filled is called a perfect BT 3. complete BT has a heap order property 4. max-heap: children have smaller value than parent node, always 5. min-heap: children have larger value than the parent node, always In a 1-indexed complete BT :- 6. parent of a node is at (i/2)th index 7. left child is at (2*i) index & right child at (2*i + 1 ) for a node at idx i 8. leaf nodes are from n/2 to nth indices In a 0-based indexing array- left child at 2i+1 & right child at 2i+2 index of node at i-th index last non-leaf node is at (n-2)/2 ⭐ or ( (n/2) -1 ) 9. insertion & deletion :  logN  10. accessing max/min element : O(1) 11.  time to build a heap-   O(n) ---------------------------------------------------------------------------------------------------------------------------- insertion in max heap- -----------------------...

Topics- Relaxation... # Topo shortest distance # BFS shortest distance (unit weights) # Dijkstra            (all, except negative weights) # Bellmen Ford   (all, except negative cycles)  # Floyd Warshall ( multi source ) # Shortest path     ( path reconstruction ) ---------------------------------- 1. Word ladder-1,2 2. Shortest Path in binary matrix 3. Min Effort Path⭐ 4. Cheapest Flights within K stops⭐ 5. Min multiplications 6. City with smallest no. of neighbours within threshold 7. No. of ways to reach a destination⭐ --------------------------------------------------------------------------------------------------------------- # Topo Shortest Dist Algo time: O(V+E) - only for weighted DAGs - works even for negative edge weights - works because in topo sorted order of nodes (nodes appearing before dependants), distance propagates correctly. ------------------ 1.  Perform topo sort & let it be stored in the stack 2....

# Detect cycle in directed graph: (DFS) the undirected graph algorithm won't work here, because we assumed that reaching a visited non parent node means we can return back, but so is not the case in directed graph. in directed graph, we say a cycle is present, if we reach a visited node which is already present in the visited path of current node ---------------------------------------------- if  in a dfs call, the curr node has no further adjacent nodes  then return false, and set pathvis =0 for this node This happens when we backtrack  ----------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------- # Topo sort-I (using DFS) - only for DAG (directed graphs with no cycles) - linear ordering of nodes such that if there is an edge b/w u & v, then u appears before v - there can be multiple topo sort orders - used to solve dependency problems ----------------...