No video :(

Priority Queue Introduction

Подписаться 177 тыс.

Просмотров 452 тыс.

50% 1

Introduction to the priority queue data structure
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
======================================
Related Videos:
Priority queue intro: • Priority Queue Introdu...
Priority queue min/max heaps: • Priority Queue Min Hea...
Priority queue insertion: • Priority Queue Inserti...
Priority queue removals: • Priority Queue Removin...
Priority queue code: • Priority Queue Code
Data structures source code repository:
github.com/wil... ===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

Опубликовано:

14 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 102

@sunnilabeouf 4 года назад

Every time I come back to refresh my memory on an algorithm or data structure, I get excited when I see that you have a video covering it. Thank you for the animations and teaching in such a clear way!

@forresthopkinsa 3 года назад

pro tip: playback speed 2x

@arjunmr2631 3 месяца назад

I also did that

@scottzeta3067 2 года назад

I love the is this a valid heap section, very useful. Newbies like me often have many “stupid questions” like these, but hardly find answers.

@demansou88 2 года назад

Been reviewing some concepts for a FAANG interview and your videos are the best for clear and concise review of data structures

@sword013 3 года назад

What a beautiful animation, my eyes were on my laptop cause the colour combination was so good to watch.

@KadaXuanwu 3 года назад

@sword013 3 года назад

@@KadaXuanwu ?

@amritaanshnarain7524 3 года назад

@@sword013 Vada Pav

@BookofYAH777 2 года назад

I don't think 7:35 is a heap because it's not a tree. In order for it to be a tree, I think each child can have only 1 parent

@taylorgerrish7264 5 лет назад

this is awesome! thanks for asking questions testing us so we can try to answer it instead of just giving the answer

@geetanjalijangid876 3 года назад

@anshulgupta7158 3 года назад

@@geetanjalijangid876 hlo

@J235304204 5 лет назад

I really liked all the example heaps.

@quocbao6046 4 года назад

I learned your Graph Theory Course to this part and I didn't understand PQ so I come here to learn it. I enjoy the way you teach with the animation and other stuffs very much. Thanks man!!

@AbdullaNabeel 2 года назад

@7:15, arent heaps always represent a binary tree but with structural ordering?

@slashtab 2 года назад

This is what I was looking, How PQ and heap is related and was getting confused b/w these two. Can't thank you enough.

@olivierkoster 4 года назад

actually, a heap also needs to be a complete binary tree. so the 3rd example is in fact not a heap.

@sandeepbhuiya4497 4 года назад

that's Correct

@HamidBazargani 4 года назад

That's the definition of binary heap. So completeness is not necessary for a heap.

@rogerthat7190 Год назад

Thank you! I couldn't find any other video on this topic

@miriyalajeevankumar5449 4 года назад

Golden content

@clashclan4739 2 года назад

Wow! more in depth videos on balancing tree and tree rotation implementation pls

@namangupta2587 4 года назад

the best video so far....nice explanation

@AdrianMei 5 лет назад

what is best first search? (same as breadth first search?)

@Charlesthebird1 4 года назад

Best first search isn't an algorithm - it's a category of algorithms which require the next-best item or thing in the data structure (where "best" is determined by a weight or a number) at each iteration (A* does this to find the next "best" movement choice for pathfinding in a graph, but the other algorithms he mentions find the next "best" choice in their respective implementations as well)

@benleung6331 5 лет назад

By your definition, a heap is a tree. However, one of the differences between a tree and a graph is that in a tree, every child can only have one parent, and yet in 7:34, the node with 6 in the third level has two parents (one a 3 and ther other is also 6), so it can't be a tree but it is a heap?

@WilliamFiset-videos 5 лет назад

Yeah, that example is questionable. Although I still maintain that the whole structure is a tree because there are no cycles. What I should have done is made the edges directed so that there is no ambiguity regarding which node is the parent/child of which.

@subbuktek 5 лет назад

Why do you think the other '6' is a parent? ...

@benleung6331 5 лет назад

@@subbuktek Because the diagram put the other '6' as one level above, the same reason that the '3' on level 2 is a parent. I know what you are alluding to, if you can assume the '6' on level 2 is a child instead of a parent, you can also assume the '3' is a child, not a parent, in that case it still can't be a heap

@mosiurrahman4061 2 года назад

Clear and Conceptual

@sarthakshah1058 5 лет назад

These videos are very well made and helpful

@spicyshizz2850 9 месяцев назад

7:44 but two things are pointing to the same node?

@darnellarford2439 8 месяцев назад

Are the edges bidirectional? I would think they only go in one direction and that displaying the edges vertically or diagonally implies a direction from the higher node to the lower node. So, assuming the edges are directional, breaking with the convention of displaying the directions from top to bottom would mean we should display them as arrows instead of lines.

@brunoserras 6 лет назад

Fantastic video! Keep up the good work.

@francois-xaviermenage4531 Месяц назад

Is that always lawful to change the root of the heap?

@subee128 4 месяца назад

Thank you very much

@onomatopeia891 2 года назад

Great explanation! Thanks!

@fatimaadreeta 2 года назад

Binary trees have at most two children, right? Not more than two. But can also have 0 or 1 child. Like showed in the max heap diagram at 6:12

@georgiyordanov4407 Год назад

When implementing, every node/element of the binary tree has a value, and two pointers. These two pointers can either point to another node (which is under the current node) or to nothing. So they can technically have 0 children, but they always have two pointers, which are both pointing to nothing.

@umairalvi7382 3 года назад

Heaps are complete binary tree or almost complete binary tree But you didn't mention it

@MGtvMusic 3 года назад

He said they don't need to be binary trees right?

@sultanahmed9694 3 года назад

I think that he made fault when validating trees mentioned in this video, I think some of them are not complete binary trees so they are not heap, since heap must be a complete binary tree

@tabarnakcalisseesti Год назад

Very good video! thanks

@anujonthemove Год назад

In short: I subscribed to you channel!

@shaygahhendricks 4 года назад

ok but the way he asked if 7 was a heap and said "yeah, it's a heap" :')

@isaacdouglas1119 3 года назад

4:05 If two elements in the priority queue have the lowest value in the queue, doesn't that mean the number polled from the queue isn't necessarily the smallest number in the queue?

@AJewFR0 3 года назад

No. This example is not how it would be implemented. In a binary tree, the order would be as his examples towards the end of the video demonstrate. You can have two nodes with the same value (priority), where they might be a child of the node that is removed. The node that is left over, would then bubble up and take the place of the just removed node.

@haykeelili8108 2 года назад

Thank you!

@natanshimeles1116 2 года назад

Heap is a complete tree, but you are referring the opposite

@YogeshDarji99 5 лет назад

Thanks for explaining concepts nicely!

@snowybutt 5 лет назад

9:40 you mean BREADTH first search, not BEST first search, right?

@nikhilk7493 5 лет назад

best is correct

@Charlesthebird1 4 года назад

@orangekitty5192 2 года назад

great stuff, who needs a CS degree?

@cathyliu9900 2 года назад

Is the heap a complete binary tree? At 7'17", the heap is not a complete binary tree.

@codeschool3964 2 года назад

Shouldn't a tree be a complete tree for it to become a heap? The second example you gave is not a complete tree right? Correct me if I'm wrong please.

@codeschool3964 2 года назад

ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-wptevk0bshY.html at here

@GURUYATHI 5 лет назад

Thank you very much for making this video.!

@omaryahia 9 месяцев назад

nice 😊👍 thanks

@shaozhetang75 6 лет назад

May I ask a question? when you took an example of what a priority queue is and the instruction asked us to add 2,4,5,9, WHY these numbers were not added with the poll operation?

@WilliamFiset-videos 6 лет назад

Shaozhe Tang I'm not sure I correctly understand your question. Could you please rephrase it? Thank you.

@shaozhetang75 6 лет назад

Yeah, from 3:35 we can see the instruction and take poll and add operations. Firstly poll() we get 1, secondly add (2) we get 2, thirdly poll() you said it happened to be 2 not 3?.... I watched the video again and realized it was because the pink circle didn't pop up with the arrow at the same time, but now I understood it. Thank you very much for your reply! your video is very good!

@WilliamFiset-videos 6 лет назад

Oops, sounds like a timing delay! Sorry for the confusion.

@pooja9587 5 лет назад

Polling means deleating not adding

@wellwell8025 2 года назад

Thanks!!!

@prabhassla4237 2 года назад

Grt explNtion

@shangluntsai6787 6 лет назад

Nice explanation, thank you

@StareLikeAWolf Год назад

do you have a code on that circles

@brentjohnrodriguez285 Год назад

deserve our prof's salary

@Mai-qr6hj 5 лет назад

I love your voice

@azeylacalaty3182 5 лет назад

I absolutely don't lol

@kirankumar2348 3 года назад

bro heaps are complete binary trees right.....

@SK-cs1by 2 года назад

Still you didn’t clear main concept on priority Queue

@romankorniienko2388 5 лет назад

u r best!11!

@huseyinmesecan9161 5 лет назад

i thought in a binary heap nodes have only one or two children nodes. 7:14min

@cloud5887 4 года назад

It’s not a binary heap, it’s just a regular heap. Only binary heaps must satisfy the requirement with up to 2 children

@sashank3 3 года назад

The complexity for building a heap isn't correct. It takes 'O(nlog(n))' to build a heap, because you are doing 'n' additions.Same would go for a priority queue too.

@spicytuna08 6 лет назад

7:16 i thought you said heap tree only applies to binary tree. this one has 3 branches. Great animation.

@benleung6331 5 лет назад

He actually said heap isn't *necessarily* a binary tree, with heaps that are not implemented as binary tree, they are called binomial heap (as opposed to binary heap)

@michaeldang8189 3 года назад

4:21 "As human we can see the numbers visually inside the priority queue, and look and know what one is the smallest to poll". Actually not quite, if we have 1 million numbers in the queue, human will have a tough time identifying the number to poll just as an inefficient programmed machine does.

@Cool.couple.channel 3 года назад

can u tell me what is heap invariant??

@bryannyeap5616 3 года назад

Watch the video?

@zihanbayeed42 4 года назад

7:39 doesn't a heap have to be a perfect tree too?

@kalebnegussie8140 4 года назад

Yes exactly. The branching factor for this heap is 3 so we cannot have nodes with just 2 children or ne child.

@Dazaromal 3 года назад

It does not have to be a perfect tree, the heap simply must be filled from left to right, if you have nodes with children then the next two nodes over at that height have no children and children respectively then that is not a valid heap. Branching factor only affects where you will start your buildHeap method whether that may be max or min, for instance if you had a heap with 3 child nodes the point at which the last possible node with children would be at will be floor of heapSize/3 (ROUGHLY) depending if were talking pseudo code and the starting index is 1 or actual code at 0.

@AJewFR0 3 года назад

A heap does not have to be a binary tree. It's typically implemented in this way though. I think that's where the confusion comes from. Although the idea of it being a perfect tree makes me think you misunderstand the heap idea. It doesn't have to be perfect (or even complete). It just has to follow the heap invariant.

@shaleen0mishra 2 года назад

Watch at 1.25x

@prabhassla4237 2 года назад

*1 2 3 4 4 5 9 8 14 22* _isn't this what first answer should be...

@Manlikerik8 Месяц назад

You sound like MoistCritikal before he got into chain smoking

@sase1017 4 года назад

Play at lest 1.25 speed, but great content

@professordrabhijitsayamber2299 2 года назад

Om shanti k

@littlem5771 5 лет назад

Priority queue != queue with priority im thinking?

@anon6975 5 лет назад

A queue is usually understood like an ordered list. A priority queue is a kind of list where it's structured so you can get things marked with a more important "priority" faster and easier. Heaps are a good way to think about implementation, but they can be implemented a number of ways.