If you're trying to write this code in Python, beware: You cannot simply assign items[0] = items[self.size - 1]. You must pop() the item at the end of the list to remove it: items[0] = items.pop() ... also be sure to use floor division in the parent calc if using Python 3: (index - 1) // 2

Storing the heap in the form of an array just blew my mind...so effective

@theinverteddonkey2961

2 жыл бұрын

it's really a tree in the form of a list of nodes

@typingcat

2 жыл бұрын

Damn, if that blows your mind, your mind most be blown multiple times a day.

@davidlee588

2 жыл бұрын

@@typingcat haha, i'm also been wondering why people easily got blown away by simply KZread videos, it must be like an ejaculation moment for them. 😂

@vectoralphaAI

2 жыл бұрын

@@typingcat mine is. There is so much to learn every day. My mind is blown on a daily basis. Its great because im never bored.

@hamzahkhan878

Жыл бұрын

what in the hell we were you thinking of if that blew your mind? lol

This is one of Gayle Laakmann's best videos. She walks us through the code, array, and tree versions while speaking calmly in a pleasant voice. Thank you!

3:22 "Aaand there we go, we've created Minecraft!"

@AlanD20

3 жыл бұрын

EXACTLYYYY 😂😂😂

Clean implementation. Clean explanation. Wonderful video! Thank you very much for taking the time to make this. I really needed it!

The explanation with the code is amazzing !! loved it....seems that would work for me! Please continue with the good work

This is a really nice explanation of min heaps.... Very nice, very clear, very simple , concise and short enough to pick up in a jiffy. Thanks Gayle.

I am translating these lessons for use in Unreal Engine Visual Blueprints, and Gayle delivers these lessons very cohesively. Thank You!

I always had problems understanding heaps, but you made it so clear. Thank you so much ...

I read about heaps online and first implemented it using a right and left Node. I felt array, though - spidey senses. I wish I would have seen it on my own. But, this video was a close second. Thank you so much for a clear description.

Just an FYI: At 3:01 timeframe, you are showing formulas and for pareint you have [Index -2) / 2]. This needs to be change dto index -1 * 2. On next screen where you are coding it, you have it right.

@Pazushh

2 жыл бұрын

I think it shouldv'e been (Index-1)/2. while "/" rounds to bottom

@calviethang7139

2 жыл бұрын

You are right!

@SupunNimantha

2 жыл бұрын

Actually that equation is not for the immediate parent of any given node but it gives you the min node (top most node ). Instead of saying parent she should have told its the min. There she made a mistake. At the same time actually there is no need to have that equation because simply the 0th element is always the min.

@dennisfolz352

Жыл бұрын

@@SupunNimantha no you are wrong. The formula (index-1)/2 returns the parent for any given node. And it is important, because you need the parent of any given node if you want to heapify up. ^^

@santjagocorkez

7 ай бұрын

@@SupunNimantha You could do the maths yourself: take the 9 at #3. Its parent is 4 at #1. Now let's compute: (3 - 2) / 2 = 0 (floor div). Oopsie, 9 at #3 has the root as its parent, while we know from the picture it's not.

Thanks you for this excellent video. It''s the best, most concise and straightforward, explanation of a heap that I've seen.

Thanks a lot, Madam. I've been burning out myself scrolling numerous websites not getting how a heap actually works and how it's implemented, and now finally implemented successfully in C#.

Her keyboard clicks are the most satisfying sound

@RobsRobotChannel

5 жыл бұрын

ASMR, wikipedia it.

@ivanleon6164

3 жыл бұрын

hate it.

@himanshusingh5118

3 жыл бұрын

😂😂😂 irritating

@sanjayvasnani988

2 жыл бұрын

Nah. It seems as if her keyboard hates being used by her.

@NilakshMalpotra

2 жыл бұрын

Agreed! Lovely sound

I forgot this channel existed. It saved me once again

I was searching for something just like this. Awesome explanation of implementation of heap.

Best video explanation with code walkthrough showing how to answer the ubiquitous lazy interviewer question "Implement a Heap data structure".

Pro tip: if your array is indexed at 1 (like with Fortran) the pointers are parent: (index-1)/2, left child:2*index, right child:2*index +1

@xMercuryx56

2 жыл бұрын

that's not pro, that's just math ... lmfao

Having that visual next to the code is such a godsent, thank you for saving my bachelors degree

Most of coders strugles to use complex abstract data structures like heaps or graphs because they dont learn it from a concrete use case.

@sarvasvarora

3 жыл бұрын

+1 for this. Doing an intro to CS course at uni rn and def if it wasn't for the coding assignments involving practical usr cases, I would've never appreciated such data structures... It's certainly very important to actually implement them in some use case in order to grasp them well.

@stas4985

3 жыл бұрын

why the hell graphs or heaps complex???

@axea4554

3 жыл бұрын

@@stas4985 because they are more complex than a simple non-resizable array or a linked list

This is the best explanation of Heap. Thanks 🙌🏻

Possible error around 2:52 The diagram shows the parent as (index-2)/2, when it should be (index-1)/2

@g.o.4678

7 жыл бұрын

I believe that calculation takes the ceiling (or whole integer value rounded up, depending on the programming language) of the operation. So, for instance, to get the parent of the node at index 7, we'd have: ceiling((7-2)/2) = ceiling(5/2) = ceiling(2.5) = 3, which is the appropriate index we're looking for.

@arvinsim

7 жыл бұрын

Gbenga Ojo

@DimaKurguzov

7 жыл бұрын

Your are right. (index-2)/2 for parent index is a mistake. Look the code at 3:22 - here is the correct version (index-1)/2.

@quangthang10d4

7 жыл бұрын

Yes I was gonna say the same thing!

@josevillegas2721

7 жыл бұрын

In python 2, / is integer division and it truncates the result so 5/2 = truncate(2.5) = 2

The calculation shown in the cartoon diagram to get the parent of the node is shown as (index-2)/2. In the code the calculation is (index-1)/2.

The video is awesome and what I needed to know. Thank you!

Very clear. Even more clear than the book actually.

This is best explanation of BST on basic concepts.

This is the most helpful code video i have ever seen

such an amazing explanation with clean code. Loved it!!!

Today I actually understand how coders actually codes and how to actually maintain the semantics of variables name fabulous explanation I sub you within 1 minutes of this video

This is awesome explanation and you are awesome.

I completely ignored about heaps. Nice explanation. Thanks!

Well done, Gayle. Thank you.

Didn't know HackerRank has itself a KZread channel. Subscribed! :)

I didn't know until now the God of programming is on youtube! Thank you ma'am! 🙏

@salman8562

4 жыл бұрын

goddess

Thank you very much miss! Awesome lesson!

Thank you, Gayle. I enjoyed your explanation and found the visual and code helpful.

Heaps can be thought of as a binary tree. Peek takes O(1) while other operations take O(log n). For min heap: 1) Insert new node at last, then heapify (ie swap with parent until parent > child) 2) Delete the root node, replace last element at root then heapify (ie swap down)

Bringing back memories of my Data Structures course Shini book it was actually good

best vid ever... thanks McDowell.

How does this not have more views?? What a simple, and amazing explanation. Subscribed!!!

@palanisamymadakkannu4350

6 жыл бұрын

only entertainment videos ll get more views.. useful videos wont get..😊

@intrepidsouls

5 жыл бұрын

Agree with you. I watched quite a lot of her videos and it seems like she doesn't quite understand what she is talking about either.

@blasttrash

5 жыл бұрын

@@intrepidsouls I agree too. Her book is good though.

@thatoneuser8600

3 жыл бұрын

Because it doesn't answer why heaps are used or when one should use them. It doesn't give a perfect concrete use-case where a heap would always be beneficial if used.

Really have to appreciate the readability of the code a variables.

I've basically watched every one of her videos before starting the chapter in my book on the topic

SO helpful - thank you so much!

Excellent explanation

This is the best explanation I've seen :) ty!

Very nice explanation. Though including big O complexity of the operations would be great.

@BryanTidwell2

7 жыл бұрын

Anwar Shaikh insertion and removal should be logarithmic. of course poll is constant and search is linear but you wouldn't want to use the structure for search

@damnstupidoldidiot8776

5 жыл бұрын

It should be O(nlog(n)).

@uusoft

4 жыл бұрын

time complexity O(nlog(n)) space complexity O(1)

@drophy

3 жыл бұрын

Insertion and removal have a time complexity of O(log(n)), where 'n' is the number of nodes in the heap. This is because for example, during insertion, in the worst case scenario, you'll need to move the inserted element from the bottom all the way up. Therefore, the max number of swaps is the height of the tree, which is log2(n) approximately (note that this is just true if the tree is balanced, but they always are for heaps). For example, her tree had 10 nodes at some point, a height of 3 (or 4, depending on how you define 'height') and log2(10) = 3.32. The max number of swaps you might need when inserting is 3. The same idea applies for removal, since the element you place at the top might need to go all the way down. The space complexity of the structure is O(n), of course, since you need an array of size 'n'. The space complexity of the 2 operations, however, is indeed O(1), since they don't need additional space.

The video feels incomplete because it never explains what a heap is used for, though the data structure very well.

@jimmithfarrel8986

7 жыл бұрын

A heap is used as a queue where the min (or max if max heap) is always accessed in O(1) time. If the min (which is always at index 0 is popped off, then the next smallest takes its place. Remember its stored linearly yet indexed logarithmically. Therefore its a "priority" queue.

@mvcds92

7 жыл бұрын

Yeah, I've googled it afterward, though it's kind of you helping me here, thanks!

@musicprod8366

6 жыл бұрын

Thank you : )

@xNajda

6 жыл бұрын

What's the difference then between a heap data set and just a normal ordered data set using a binary search for the placing of each new element?

@sumitbhattacharya1720

6 жыл бұрын

go read a book then.

this is useful for priority queues

@tamoorhamid519

4 жыл бұрын

That's one application.

@jadanabil8044

3 жыл бұрын

@@tamoorhamid519 what are the other applications?

@tamoorhamid519

3 жыл бұрын

@@jadanabil8044 They can be used to efficiently find the largest or smallest value in an array.

Great explanation of heaps

I have final exam tomorrow, after this explanation, if this will be my pick, I know I'm safe. Amazing videos!

@utkarsh_108

4 жыл бұрын

Best of luck

@ShermanSitter

4 жыл бұрын

I don't have an exam, but i found it useful as well! I don't know why, but heaps were so confusing...until now! :)

@ShermanSitter

3 жыл бұрын

@Chris Chu Learns ah shucks. thank you!

@kenansari

3 жыл бұрын

how it was?

@Itskfx

Жыл бұрын

Same, I'm terrible at heaps. These vids help a lot!

Super clear explanation .

excellent work!

Not sure if she explains this clearly but keeping the array operations to O(1) is probably accomplished via using swaps, where the indices to be used by the swap are found in O(1) by using parent/left/right references?

This is so simple and easy to understand. A+++++++++++++++++++

Very good explanation!

Except a small mistake this video is a great resource in understanding heap data structure. Thank you. :)

Thanks for the video! But I am a bit confused about the smallerChirld at around 10 min. Should the left child always be the smaller one?

Curious how rightChild, leftChild hasParent english syllabuls used here are actually implemented when we are dealing with arrays :) May be doable but will turn brain teaser. I guess one would prefer to use classes at that point. In any case this video is worthwhile and very relevant. Thank you Gayle.

Amazing explanation!!!

hasParent method should be simplified to: hasParent(int index) {return index > 0}

@randomrandom316

4 жыл бұрын

Its quite clever

@brianspinos

3 жыл бұрын

Nice!!!

Awesome explanation. Healped me a lot. Thank you.

For heapingDown, what if instead of the left child being swapped, the right child was being swapped, and the new node would get bubbled down to a place that exceeds the size? then the heap will no longer be compact and there would be empty spots, no? So we'd need additional implementations to take care of this case

Thanks for this.

What overhead will you get from an array of class?

I didn't figure it out how main should look like. Could you give me some tips? Thank you! Keep up the good work!

Excellent explanation :)

Great and concise

When I clicked on this video I had no idea I'd be learning from the legend herself. Damn.

After you poll(), shouldn't you remove the element at `items[size - 1]`?

For deleting a node, is there any issue with just not moving the last node up and bubbling up the smaller child of the empty node until there are no children, and then moving the remaining indices left by 1? Is it less efficient, does it cause any problems, or is it just that we want to heapify down since we already have that method for other purposes anyway?

There is error at 2:56, parent is (index - 1 ) / 2 Or otherwise for left node we get (parent -1) instead of parent. Everything else is just brilliant, thank you for the Great Explanation! 💓

@Itskfx

Жыл бұрын

Noticed that too, but I think they corrected that in their code implementation. lmk if I'm wrong cause I'm here for exam revision and I'm kinda weak at heaps.

Why do I relate to that node that is all empty inside! xD

Easy to understand!

That was great , could you also post an explanation of Iterative Heap Sort algorithm this simple way!!

Concise and crisp

Note: formula for getting parent index, in the diagram is different from the actual formula used in the code. In Diagram - Wrong, In code - Correct

Possible error at 1:54 the algorithm is said to be swapping with the smallest of the 2 child elements (when bubbling down) So 20 is swapped with 4, then the pointer is swapped with 9 (left child) while the right child is 7 - smaller.

@nopenope8409

5 жыл бұрын

1 year later but that is not correct because what you see there is already swapped so there was 4 before the swap and 20 took the place of 4 and then took the place of 9. there isn't an error

What is the time and space complexity ? And what are the effective use cases for min/max heap?

Thank you :D

is it book in russian on the table behind Gayle? :)

So in this array, the entire time the last subscript will be empty? I ask because when you add a new value to the heap you first put it in the last space in the array then you increment right after.

Method hasParent will return true for root node as well. Because for rootIndex =0, getParent will return 0, because (0-1)/2 = 0. Hence, use of hasParent at line #55 has no effect. To fix this, hasParent can simply return true for all nodes if their index > 0.

so simple to impliment, just paste these blocks of code and *BAM* it probably does stuff but good luck explaining it on an interview

may i ask, is it true that the array index will always start from 1 for the root in the heap? but your video said it will start from 0? Thank you !

Minor mistake, at 8:23 instead of comparing the indexes of the left and right children, you should be comparing their values to get the smaller child!

@adityamedhe

2 жыл бұрын

that's not minor

We need to have one more line in the "poll()" method, correct me if I am wrong. I used the starting example (after inserting 3 as new value to heap) to test the same. int item = items[0]; items[0] = items[size - 1]; items[size - 1] = 0;//We need to make the last element zero explicitly as the last element will stay otherwise. size--;

@dishantsheth9592

5 жыл бұрын

The "size" variable maintains the boundary of the heap in the array and so there isn't a necessity to take care of elements with index >= size in the array. Also, "items[size-1] = 0" doesn't achieve the same result as assigning a dynamic node in a tree to null. Here, it simply gets assigned a value of 0. To help with understanding, consider the pop operation in the static implementation of a stack. The popped values remain in memory after pop but not in the stack because of the "TOP" pointer there. Similarly here, size keeps track of the boundary of the heap to help with add and poll operations.

How can I insert String objects to the Heap if it is an Array? Or should I use and ArrayList

Great video thank you

That butterfly keyboard sound 😕

Her way of writing the code... thats impressive

In the heapifyUp() function why do you have to reassign index = getParentIndex(index) when the swap function does that for you

0:06 i forgot it just after 2mins watching this video, and so watched again🤐

There is an animation on 1:49 which not reflects the actual logic of the heap sink down ( accordingnaly to the idea of swaping with smallest child node when bubbling down )

The video should also talk about the run time complexity of the functions implemented

@wotizit

3 жыл бұрын

should O(nlogn) worst case

Correct me if I am wrong but I think that adding 1000 (or any number greater than 7) and then adding 5 (or 6 or 7 as well) to the heap example at 3:00 would result in an error if the heapfyUp() code provided further in the video is used. Namely, the top node would be the second number added (5 or 6 or 7) which would be greater than the left hand side child.

@bigbangind

7 жыл бұрын

I don't think so

@supportteam2007

7 жыл бұрын

Me neither. haha I guess I wasn't paying too much attention.

very good pseudo-codes.

Also, what happens if you pass 0 as an index into parent()? You'll get back -1 from getParentIndex since (0-1)//2 == -1, and then you'll get an "index out of bounds error" in some languages or worse, you'll get the last item in the list in python!

yes I got everything thank s a lot !

Nice explanation

I don't know, but is getParent(index) correct? If I get the final heap of the example, like: [10, 15, 20, 17, 25] and I add an element in the end, for example, 32 and it would be below 17, so 17 is 32 parent. 32 index is 5. 17 index is 3. If we use getParent(5), I would have: (5 - 1) / 2 => 4 / 2 = 2 But index 2 is not 17, but 20... Am I missing something here?

@dmitrybahtiarov3555

2 жыл бұрын

There is error at 2:56, parent is (index - 1 ) / 2 and not (index - 2) / 2