for those who came for details for min binaryheap from tushar's dijkstra algorithm video, watch from 1:15 to 5:55. cheers !
@NohandleReqd4 жыл бұрын
Now this is some helping out!!!
@PROcrastiDRIVESVofficial7 жыл бұрын
You can really teach. Thank you for all your hard work. You're the exact opposite of all those professors clogging up the halls and offices at uni, because you can actually make this stuff easy to understand for human beings.
@JAlternative1067 жыл бұрын
Your explanations of these graphing algorithms by far the the most thorough and clear. thank you so much for doing these.
@HemantKumar-cb2uz5 жыл бұрын
the ease and confidence in the voice adds clarity to the solution, i like it
@ameyapatil11398 жыл бұрын
You are the boss ! I simply love your tutes !
@nicholaslarovere60376 жыл бұрын
Very well done - I appreciate your pacing throughout the lesson. You start the video building the foundation we need to then understand later parts of the lesson - that is key!
@akashnayak3752 Жыл бұрын
from the last 7 days was stuck with a particular doubt. Was losing my mind over it! 7 mins into the video and my doubt is cleared. Thank you so much. May the Gods bless you.
@ManojSingh-eu1js8 жыл бұрын
Sir, You are an excellent teacher and a wonderful person to help a lot of needy ones like me here. Thank u so much. Please keep up the good work!
@karansaxena44226 жыл бұрын
Hi Tushar, hats off to you for investing so much of your time in this channel! This helps a lot of people!
@shaunakchadha49617 жыл бұрын
You are one of the best Data Structure teachers............Far better than the ones in our college
@gauravsrivastava94282 жыл бұрын
Thanks for the great explanation. One point which is not mentioned in the video is that this is eager implementation of Prim's algorithm. There exists a lazy implementation of prim's algorithm with a different implementation. However, the basic idea remains the same.
@mirahmed50238 жыл бұрын
Neat, clear and thorough presentation. I am certain that you are helping a good chunk of students who do not get enough from their professors' lectures. Thank you and keep up the good work (y).
@mirahmed50238 жыл бұрын
+Tushar Roy btw Tushar, it would be very helpful if you could do tutorials on sorting algorithms, especially the advanced ones such as quicksort, mergesort, shellsort.
@amirthakatesh63607 жыл бұрын
Thanks a ton!! All your videos are extremely helpful ,especially before exams! Upload more videos as much as possible, you make things look so simple and easy.
@FarhanMohammedKN8 жыл бұрын
Thanks for the video, Awesome explanation
@tommyw53327 жыл бұрын
I may be mistaken, but I think the operation while he's visiting C and replaces the AB edge of cost 3 with the BC edge of cost 1 is incorrect. Again, I may be mistaken here, but I was under the impression you have to compare the cost of the edge (BC: 1) with the total cost to get to the edge from A (AD: 1 + CD: 1 = 2), or 2+1 = 3, and since 3 is not less than the current value stored, B's path to edge (AB: 3) is not overwritten. I think what was done here in this specific case (just the CB edge, not the rest), was similar to how edges are selected for Kruscal's algorithm. BC is still a valid edge of one of the MSTs of this particular graph, but what I'm saying is the reasoning of WHY the decision to replace AB with BC was incorrect under Prim's algorithm. In other words, with his reasoning, if the edge BC was weighted 2, he would have still selected BC as the new edge to get to B from A, which would have resulted in a non-minimum spanning tree (ADCB: 1+1+2 = 4 vs AB: 3).
@NohandleReqd4 жыл бұрын
Hey man. Yours are some of the best and simplest videos for these weirdly complex data structures. Keep up the good work. Also, as you are handling complex stuff, could you start making videos for different complex Dynamic Problem? It will be a great help.
@TheAmonkeys8 жыл бұрын
Your tutorials and explanations are awesome, keep it up!
@dance2die5 жыл бұрын
Thank you, Tushar. The explanation was nice and clear.
@AakankshaDevgan7 жыл бұрын
You teach unbelievably well! Perfect!
@saitaro8 жыл бұрын
Your videos are really helpful. You got talent for this stuff.
@KirubaEbenezer8 жыл бұрын
Saving me in exam time... For placement preps it is very useful... do more videos as much you can... lol
@nancyhada44807 жыл бұрын
You are really an amazing teacher.
@pradyumna277 жыл бұрын
Appreciate your efforts. Thank you for the video. It helped allot.
@Dule436 жыл бұрын
Than you vary much for this video. You helped me a lot to understand this algorithm!
@vigneshwarp34627 жыл бұрын
Nice explanation Tushar.. Thank you very much.
@zishunokia62338 жыл бұрын
Fantastic Explanation! Best i have seen on youtube... Keep it up... Waiting for more uploads.. Thanks
@amith89rm4 жыл бұрын
Hi Tushar, Thanks so much for your videos. Keep these videos coming. It helped in understanding algorithms so well. I used to spent lot of time to understand algorithms but your videos helped me in understanding in less than 20 mins. Thanks so much for the videos. I did feel you are talking a little faster but i changed the video playback speed :) Cheers!!!!
@ningwang80778 жыл бұрын
Very very clear, Oh you do a great job!
@sahildhawan228 жыл бұрын
I now type algo name Tushar Roy in KZbin search bar for my exams! :) But plz see my doubts in your DP videos.
@hemanshu05034 жыл бұрын
@Tushar It looks like the space complexity should be O(V) as we're only going to store a single edge per vertex, did I miss anything?
@user-jo2eu3wu1g5 жыл бұрын
Really great explanations. Thanks!
@bogdanboariu91078 жыл бұрын
Great videos ! Thanks for the explanations !
@diogodias26347 жыл бұрын
mate because of you i could do one problem at university, thank you and good luck :-* (sorry for the bad english, not my native language)
@ganapatibiswas58584 жыл бұрын
Great lesson
@shreyassingh62034 жыл бұрын
Hey Tushar, At any points we are only storing V vertices and V edges. So space complexity is O(V) not O(E+V). Think and you will realise. Ps- We are always storing V edges and never storing E edges. |E| can be O(V) in special cases but still space complexity remains O(V+E) = O(V). For |E| of order O(V^2) we are only storing V edges, so space complexity remains to be O(V). Give it a thought, and you will get it. Map of result has V keys, Heap + Map will have at most V nodes, and result list will have V-1 edges. Its all V edges + V vertices.
@yifeigong1356 жыл бұрын
Thank you so much Tushar!
@yashkant5598 жыл бұрын
Appreciate your efforts!....great one.... :)
@saikirankolusu61658 жыл бұрын
Thank u sir for all u'r videos we are getting so much of knowledge about the subject.i want skip list information, program.
@vikramadityakukreja47957 жыл бұрын
As someone who doesn't use c++ for competitive, Tushar's java code is extremely useful :P
@WorldOfPersianDoc8 жыл бұрын
thanks a lot for your good explanation.
@madhukiranattivilli23212 жыл бұрын
Should use D-ary heap instead of Binary heap w/ Prim's MST algo. D is tree order (i.e. max # of children of any node). D=log2(V) (D=E/V is another way, but log2(V) gives better performance). removemin and decrease are the 2 prominent OPs among which decrease is more frequent (O(E), removemin at O(V)). decrease causes swim whereas removemin causes sink. swim causes comparison b/w a node with it's parent, all the way till the root if required, whereas sink causes getting the smallest among all children and comparing that with the node, all the way till final level if required. So swim performs better with D-ary heap whereas sink performs better with binary heap. But since swims are more frequent than sinks, D-ary heap has to be used with D=log2(V) to strike a balance in the performance of sinks and swims. sink and swim run in O(log2(V)) time with binary heap. With D-ary heap they run in O(log(V)) time =~ O(log(V)) time
@aviralruhela53896 жыл бұрын
THANK YOU !!!!!!! Got it all in first time!
@mrinalmandal9147 жыл бұрын
bro u are just awesome, keep it up , plz upload more videos
@aayushtakkar78718 жыл бұрын
Thanks .. best lecture representation..!
@ianpinero97737 жыл бұрын
Thank you so much Tushar :)
@warAlgorithmm8 жыл бұрын
perfectly explained!!..thank you
@mukundsridhar42506 жыл бұрын
Brilliant as usual.
@aadil4236 Жыл бұрын
Nice explenation. I think kruskal algorithem for MST is way simpler.
@muhammadatharkhan86957 жыл бұрын
Amazing explanation ! :)
@anandzutshi3578 жыл бұрын
Hi! Really enjoyed your tutorial. Would be great if you could upload videos on graph colouring problems.
@saadnnoor9 жыл бұрын
your tutorials are pretty good :) please upload your tutorials on Number theory :)
@nithyasundar847 жыл бұрын
Tushar.. Do we really need resultList as the vertexToEdge map itself holds all the edges required for the result? Can the vertexToEdge map acts as the result set?
@varun54138 жыл бұрын
nice explanation
@kumarsahastranshu66477 жыл бұрын
very nice....!!
@nishpatwa0076 жыл бұрын
Hi, I have one question Instead of storing the edges in the result set can't we just print the values of hashmap at the end to print the result ,since the values will be overridden whenever there is an update of weight?
@lokeshaggarwal51296 жыл бұрын
bhai aap great ho!!!!
@troysincomb7 жыл бұрын
It's faster to just trace the smallest immediate edge for a test. This is just what the algorithm has to do.
@timetraveller36476 жыл бұрын
no
@vaibhavkumar9036 жыл бұрын
Shouldn't the order be ['AD', 'DC', 'CB', 'CF', 'FE'] where CD->DC ,BC->CB, EF->FE. he started with ( smallest element in dictioary+visited vertices) but later he changed the order. Correct me if i'm missing anything here
@ayushmalpani88657 жыл бұрын
Thankyou for the video!! Can you please upload the link of how to construct heap + map datastructure in c++ . I am not able to find it.
@weiak117 жыл бұрын
This one is great
@ankitdulani7 жыл бұрын
what would be the cost of traversal for 9 or 10 as once a person has reached B node it need to return to C so that it could traverse further
@ankitnegi58208 жыл бұрын
mast..
@karthiksar17 жыл бұрын
Hi Tushar,Really loved the way you explained!!!In binary heap of ur code,i have a doubt,wen you update NodePosition map,y dont u update allNodes position.Because in few areas of your code you take node depending on postion from map.
@MrRys7 жыл бұрын
shouldn't the decrease function work so that decrease(f,2) would subtract 2 from (f,7) and reposition it's location in the tree? so instead of repositioning (f,-2) as is in the video, it should reposition (f,5)?
@dipal0427 жыл бұрын
Excellent explanation! Keep it up. If 2 edges are found with same weight , which edge should I choose? After Step1, Can I choose edge BD instead of edge AB?
@priyaranjansingh68147 жыл бұрын
A graph can have more than one minimum spanning tree. So, while traversing in the graph if you will find two edges of same weight then you can choose either first one or second one. Output will result in two different minimum spanning tree.
@divyanshupreti34346 жыл бұрын
Awesome!
@Austin-hm6qq7 жыл бұрын
Thanks man!!
@marcusaureliusfanboy7 жыл бұрын
At 2:07,I see why contains() is O(1). But why is findMin() O(logN).Shouldnt it be O(1) since you can directly access the heap root in O(1). Correct me if I am wrong.
@marcusaureliusfanboy7 жыл бұрын
I see where I went wrong. For anyone having the same doubt,peeking the min value i.e just reading the min value takes O(1). But in extractMin(),the min element is not only read but also removed from the heap,so readjusting the links in heap takes O(logN).
@aishwarysingh62774 жыл бұрын
while calculating the cost of the path you are ignoring the weight of the node
@MessiLionel1238 жыл бұрын
the complexity of heap contains is O(n) as it needs to search all elements.
@chuxv8 жыл бұрын
+Lionel Messi a MAP is used to speed up that operation at the cost of space. MAP stores key => position , HEAP is implemented using an ARRAY, meaning, it takes almost O(1) (depending on the quality of your HASH FUNCTION) to find an element (and thus the position in the ARRAY), from there is O(1) to get the element from the HEAP since you already now its position. This implementation achieves good speed at the cost of waisting a los of space: Graph (adjacency list): O(V+E) Heap (array) = O(V) + Map (HashTable) = O(V) MST List of Edges = ~O(V) MST Map = ~O(V) As you can see, for a 40MB graph we are looking at a very expensive implementation in terms of memory allocation. Time also gets a huge hit on performance. Think of it this way: it is not the same looking for a shoe in a house than looking for it in a Football stadium. Now, since he is using java, think of the garbage collections (which are blocking calls). If you use a lot of space it will be reclaimed sooner or later (most likely sooner). All in all, time complexity is very relative when you do not understand the big picture.
@MessiLionel1238 жыл бұрын
+Chucho Valladares Excellent thanks for the clarification :)
@MessiLionel1238 жыл бұрын
+Tushar Roy Keep up the good work bro.
@sakinafatima4 жыл бұрын
thankuuuuuuuu
@akashkalia66236 жыл бұрын
How the vertices and edges of graph is used to construct Minimum Heap ?
@leozilla5 жыл бұрын
you where talking a little faster than in your other videos, for me it was a little too fast, pls slow it down a bit next time
@jawwadismail94194 жыл бұрын
Y don't u use playback speed option 😀
@harshitagarwal51888 жыл бұрын
if we are implementing this in c++ then i think it would be better to use STL set instead of STL priority queue since when we gonna be updating the edge in the priority queue first we need to erase it and then insert it again and since priority queue doesn't have erase method but set has , it would be better to use set. i am a novice, please correct me if i am wrong.
@chanlongtieu52978 жыл бұрын
Why do you extract F after B is all checked?
@BrewingHappinessrocks8 жыл бұрын
oky thank you and if we are simply given a que to solve a spanning tree which is directed ..so which method to use ?
@ritesh41655 жыл бұрын
Sir how can we impliment decrease key operation in priority queues in java .......as heaps can also be created using priorityqueue in java
@adityabharadwaj20494 жыл бұрын
I love you bro.
@paolocarroll29157 жыл бұрын
what happens when u try to extract min and there are two with the same value
@suhasnayak47045 жыл бұрын
In Binary Heap implementation, for node class he has used weight. Can anyone tell me what is the purpose of using weight attribute for node class ?
@roxtriv7 жыл бұрын
Why would it use O(V + E) auxiliary space? Heap would have maximum V vertices and map would store only 1 edge per vertex(the edge with minimum path to that vertex).
@just_browsin7 жыл бұрын
somebody please explain this. I was thinking the same thing Heap has at most V space , map would be same thing. In the arraylist where you store the minimum edge that contributes the vertex that is V space as well and the answer array is at most V space as well right? because it's a minimum spanning tree so you're only going to have the number of edges needed to connect all the vertices which can't be more than the number of vertices so V again...so 4V in total so O(V) space seems correct. Somebody tell me why I'm wrong
@elllot_7 жыл бұрын
It's because you have to store the weights some how and the only way to do so efficiently is to generate a hashmap of each weight. Also you would need to keep track of the connectivity (adjacency) list of each node so doing which basically outlines all edges.
@gauravseta7 жыл бұрын
where is binary heap video on your channel? I dont find it anywhere in any of playlists .
@szabyka166 жыл бұрын
Ty :D
@RahulRajav8 жыл бұрын
Thank you very much sir for your tutorials,the way you explain is really nice but i request you to suggest me source from where i should study java so that i can be able to implement these graphs logic using predefined function P.S-I know collection framework,but not method such as getAllVertexForEdge()
@RahulRajav8 жыл бұрын
I thought those are predefined method and i don't know.well,thank you very much sir
@AP-eh6gr8 жыл бұрын
+Rahul Raja use JgraphT library
@AhmadAwais6 жыл бұрын
Can you check if the formulae you had for children and parents were right? Coz. in Binay Heap this is how I implement it. - Left child: 2 * i - Right child: 2 * i + 1 - Parent: i / 2
@adityamittal43576 жыл бұрын
His formulae are right. So are yours. It's because he started the index of root node at 0 and you started it at 1. The formulae depend on how you index.
@puchob28 жыл бұрын
excellent explanation, too bad that priority queues does not exist in C#
@infotechagentdotcom30708 жыл бұрын
Thank you boss! You are good. what if i want an interface to display the graph, as input and the output will also be displayed in form of graph (to solve general problems) with each of the iterations (with table displayed). How can this be implemented using java. Thank you
@cch81558 жыл бұрын
Tushar Roy your video is great! i learned a lot! but i have a question. why is the time complexity for the heap 'contains' operation O(1)? i guess we need to loop through all the map and check if 'B' contain in the map... is not that O(n)? thanks
@cch81558 жыл бұрын
thanks~
@cch81558 жыл бұрын
btw do you know how to solve traveling sales men with branch and bound? thanks i know how to solve it by dp but it take too many space if i have 25 cities . thanks a lot!
@sakshamagarwal82447 жыл бұрын
Why is the complexity not VlogV?
@shivamkanodia3846 жыл бұрын
can you please write complete implementation of priority queue with decrease key operation?
@jacksonarnold967 жыл бұрын
when do you insert things into the binary heap
@gursharan7496 жыл бұрын
how edges are stored in graph?
@susanladart46078 жыл бұрын
Your implementation does not give a MST for the following example. Every time you add a vertex (using min heap), your algorithm does a BFS only on one vertex. But instead, you should do a BFS on all the vertices of the intermediate MST. For e.g. if AB = 2 (instead of 3), BD = 4 (instead of 3) and DC = 3 (instead of 1), your implementation would still give the same result which is AD, CD, BC, CF, FE (length = 11). However, the correct solution is AD, AB, BC, CF, FE (length = 10) which is the MST.
@ChandraShekhar-by3cd6 жыл бұрын
Sir Where can I find the Code for Prims Algorithm using C++ STL?
@anubhavanubhav76515 жыл бұрын
great exPL!
@BrewingHappinessrocks8 жыл бұрын
is the process same for directed graphs?
@conradosanchez73327 жыл бұрын
The source code on GitHub called primMST is missing a couple of class source code files such as Edge, Graph, and Vertex. Where are they?
@tushar.bansal_7 жыл бұрын
here it is- github.com/mission-peace/interview/blob/master/src/com/interview/graph/Graph.java
@yashmittal63536 жыл бұрын
how does this algorithm avoid cycle?
@sonudoo8 жыл бұрын
Is there any way to implement maps in C?
@marriagedance86576 жыл бұрын
Why does extract min takes O(logn) time ? We only need the first element of the heap, so shouldn't it be O(1) ?
@MrRounaksoni6 жыл бұрын
After extracting minimum element, it disturbs the property of minimum heap. So we have to call heapify function which takes O(logn) time to convert it into minimum heap.