Learn about heaps. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank.com/domains/tut...
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!
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
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.
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.
@@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. ^^
@@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.
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.
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#.
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.
+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.
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
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?
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.
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.
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
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.
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.
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
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.
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
I am getting 404 when I am clicking on the link given in the description. I have tried to find the Cracking The Coding Interview Tutorial on hacker rank on the website, no luck there as well. Can anyone help? Thanks
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.
Wouldn't the equation for the parent node @2:55 be incorrect? For example, Index 9 with the value 13. if you take (9-2)/2 you get 3. Index 3 is parent of 15 and 20, not 13. Node 7 at index 4 is parent to Node 13 at index 9, so the equation was wrong? Am I missing something? Thanks
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--;
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.
At 9:03, she moves the updating of index to outside the else block. I'm thinking you could move both lines outside it and get rid of the else branch. Anyone disagree?
You would have to re-write the code as follows : if( items[index] >= items[smallerChildIndex] ) //Notice the change in the binary operator from < to >= { swap(index, smallerChildIndex); } index = smallerChildIndex;
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.
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!
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)
To remove an arbitrary element, again, replace it with the element in the last position and decrease the the size. If the element is less than the removed element, then heapify up, else, heapify down.
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?
So, is the relationship between heap and tree similar to the relationship between stack/array or stack/linked list? I.e. it's a heap at the higher level of abstraction, and the implementation behind the scenes is another data structure?
at 2:55 to 3:03 ..What if we are at first position in the heap and if we apply (index-2)/2 to get to root node then (1-2)/2=-1/2.But there is no -1/2 position in the heap array?
Actually the formula is (index-1)/2. Its wrong in the video. n if u want to calculate the parent of root the position will be 0. It is also logical to use Int variable for calculating the position in an Integer form.
Can anyone how'd it have to change in order for it to function as max heap? Currently I assume I'd have to use heapifyDown in the add function instead of heapifyUp?
I was wondering that myself. My guess is that it's to avoid confusion with object oriented getters that report the value of private members but leave them unchanged, the way peek() does.
so it doesn't actually get deleted per-say. When we decrement the size variable we are essentially placing the last item out of the array and the next call to add() will overwrite it.
Storing the heap in the form of an array just blew my mind...so effective
it's really a tree in the form of a list of nodes
Damn, if that blows your mind, your mind most be blown multiple times a day.
@@typingcat haha, i'm also been wondering why people easily got blown away by simply CZcams videos, it must be like an ejaculation moment for them. 😂
@@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.
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!
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
Why not though?
Clean implementation. Clean explanation. Wonderful video! Thank you very much for taking the time to make this. I really needed it!
3:22 "Aaand there we go, we've created Minecraft!"
EXACTLYYYY 😂😂😂
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.
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.
I think it shouldv'e been (Index-1)/2. while "/" rounds to bottom
You are right!
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.
@@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. ^^
@@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.
I am translating these lessons for use in Unreal Engine Visual Blueprints, and Gayle delivers these lessons very cohesively. Thank You!
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.
I was searching for something just like this. Awesome explanation of implementation of heap.
I always had problems understanding heaps, but you made it so clear. Thank you so much ...
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#.
Thanks you for this excellent video. It''s the best, most concise and straightforward, explanation of a heap that I've seen.
Possible error around 2:52
The diagram shows the parent as (index-2)/2, when it should be (index-1)/2
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.
Gbenga Ojo
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.
Yes I was gonna say the same thing!
In python 2, / is integer division and it truncates the result so 5/2 = truncate(2.5) = 2
I forgot this channel existed. It saved me once again
Her keyboard clicks are the most satisfying sound
ASMR, wikipedia it.
hate it.
😂😂😂 irritating
Nah. It seems as if her keyboard hates being used by her.
Agreed! Lovely sound
Best video explanation with code walkthrough showing how to answer the ubiquitous lazy interviewer question "Implement a Heap data structure".
Having that visual next to the code is such a godsent, thank you for saving my bachelors degree
The video is awesome and what I needed to know. Thank you!
This is awesome explanation and you are awesome.
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
that's not pro, that's just math ... lmfao
Most of coders strugles to use complex abstract data structures like heaps or graphs because they dont learn it from a concrete use case.
+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.
why the hell graphs or heaps complex???
@@stas4985 because they are more complex than a simple non-resizable array or a linked list
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
I completely ignored about heaps. Nice explanation. Thanks!
This is the best explanation of Heap.
Thanks 🙌🏻
Thank you very much miss! Awesome lesson!
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.
such an amazing explanation with clean code. Loved it!!!
Very clear. Even more clear than the book actually.
Didn't know HackerRank has itself a CZcams channel. Subscribed! :)
SO helpful - thank you so much!
This is best explanation of BST on basic concepts.
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?
What overhead will you get from an array of class?
How can I insert String objects to the Heap if it is an Array? Or should I use and ArrayList
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.
I have final exam tomorrow, after this explanation, if this will be my pick, I know I'm safe. Amazing videos!
Best of luck
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! :)
@Chris Chu Learns ah shucks. thank you!
how it was?
Same, I'm terrible at heaps. These vids help a lot!
How does this not have more views?? What a simple, and amazing explanation. Subscribed!!!
only entertainment videos ll get more views.. useful videos wont get..😊
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.
@@intrepidsouls I agree too. Her book is good though.
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.
In the heapifyUp() function why do you have to reassign index = getParentIndex(index) when the swap function does that for you
Very nice explanation. Though including big O complexity of the operations would be great.
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
It should be O(nlog(n)).
time complexity O(nlog(n))
space complexity O(1)
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.
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.
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
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 !
I didn't know until now the God of programming is on youtube! Thank you ma'am! 🙏
goddess
Thank you, Gayle. I enjoyed your explanation and found the visual and code helpful.
This is the most helpful code video i have ever seen
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.
For the sake of curiosity, how can we implement a heap with with left and right nodes ?
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?
Awesome explanation. Healped me a lot. Thank you.
I've basically watched every one of her videos before starting the chapter in my book on the topic
Well done, Gayle. Thank you.
What are the key differences between a min heap and a binary search tree?
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
I am getting 404 when I am clicking on the link given in the description. I have tried to find the Cracking The Coding Interview Tutorial on hacker rank on the website, no luck there as well. Can anyone help? Thanks
The video feels incomplete because it never explains what a heap is used for, though the data structure very well.
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.
Yeah, I've googled it afterward, though it's kind of you helping me here, thanks!
Thank you : )
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?
go read a book then.
I didn't figure it out how main should look like. Could you give me some tips? Thank you! Keep up the good work!
Wouldn't the equation for the parent node @2:55 be incorrect? For example, Index 9 with the value 13. if you take (9-2)/2 you get 3. Index 3 is parent of 15 and 20, not 13. Node 7 at index 4 is parent to Node 13 at index 9, so the equation was wrong? Am I missing something? Thanks
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--;
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.
Bringing back memories of my Data Structures course Shini book it was actually good
At 9:03, she moves the updating of index to outside the else block. I'm thinking you could move both lines outside it and get rid of the else branch. Anyone disagree?
It's more readable and less code, but "else" gives you an idea of flow.
You would have to re-write the code as follows :
if( items[index] >= items[smallerChildIndex] ) //Notice the change in the binary operator from < to >=
{
swap(index, smallerChildIndex);
}
index = smallerChildIndex;
Is there any particular reason why you didn't use an ArrayList?
hasParent method should be simplified to:
hasParent(int index) {return index > 0}
Its quite clever
Nice!!!
Except a small mistake this video is a great resource in understanding heap data structure. Thank you. :)
is it book in russian on the table behind Gayle? :)
This is the best explanation I've seen :) ty!
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.
I don't think so
Me neither. haha
I guess I wasn't paying too much attention.
what is the reason you set the helper methods as private and others for public?
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!
Great explanation of heaps
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)
How do you remove an arbitrary element? She only wrote a method that deletes the root...
To remove an arbitrary element, again, replace it with the element in the last position and decrease the the size.
If the element is less than the removed element, then heapify up, else, heapify down.
That was great , could you also post an explanation of Iterative Heap Sort algorithm this simple way!!
best vid ever... thanks McDowell.
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?
why are we swapping indices instead of elements in the heapifyUp method?
this is useful for priority queues
That's one application.
@@tamoorhamid519 what are the other applications?
@@jadanabil8044 They can be used to efficiently find the largest or smallest value in an array.
Please fix error in parent index formula
is there anywhere that lists the pros and cons of implementing heaps using arrays and Linked Lists
Arrays do work amazing tho!
Really have to appreciate the readability of the code a variables.
Amazing explanation!!!
After you poll(), shouldn't you remove the element at `items[size - 1]`?
This is so simple and easy to understand. A+++++++++++++++++++
So, is the relationship between heap and tree similar to the relationship between stack/array or stack/linked list? I.e. it's a heap at the higher level of abstraction, and the implementation behind the scenes is another data structure?
yes. But heap is not usually implemented as a tree (but it can be)
2:15 and where would you store the value for the node ?
Maybe a hashmap
At @2:49, isn't parent = (index - 1) / 2 like the code uses ?
What is the time and space complexity ? And what are the effective use cases for min/max heap?
at 2:55 to 3:03 ..What if we are at first position in the heap and if we apply (index-2)/2 to get to root node then
(1-2)/2=-1/2.But there is no -1/2 position in the heap array?
Actually the formula is (index-1)/2. Its wrong in the video.
n if u want to calculate the parent of root the position will be 0.
It is also logical to use Int variable for calculating the position in an Integer form.
I saw an error at 3:04 . Parent is (index-1)/2 instead of (index-2)/2
At 2:51 How do you know that the element at the top will still be minimum after insertion?
Aditya Chawla what do you mean? The algorithm for addition doesn’t change based on the underlying storage tool
It should be (index-1)/2 for the parent and not (index-2)/2. Please correct it.
Can anyone how'd it have to change in order for it to function as max heap?
Currently I assume I'd have to use heapifyDown in the add function instead of heapifyUp?
why not 'get()' instead of 'poll()' ??
I was wondering that myself. My guess is that it's to avoid confusion with object oriented getters that report the value of private members but leave them unchanged, the way peek() does.
Why call it poll() to remove the minimum element, instead of pull()? Typo?
Could someone tell the name of the software, that is used in 6:23 to paint on your screen while doing something else, in this case coding?
Can some tell me please What font is used in the video code?
are there in java inself heapifyDon and Up methods?
What software is she using to show the handwritten aids?
where is the code that actually deletes the number 25 at the bottom at 9:22 ?
so it doesn't actually get deleted per-say. When we decrement the size variable we are essentially placing the last item out of the array and the next call to add() will overwrite it.
Very good explanation!