Learn about heaps. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank....
Пікірлер: 464
@Saztog14253 жыл бұрын
3:22 "Aaand there we go, we've created Minecraft!"
@AlanD203 жыл бұрын
EXACTLYYYY 😂😂😂
@lilypad51822 жыл бұрын
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
@owinophil5777 Жыл бұрын
why are we swapping indices instead of elements in the heapifyUp method?
@stevenmarsh40515 жыл бұрын
What software is she using to show the handwritten aids?
@martinduva13396 жыл бұрын
Excelent video! Helped me so much, thank you
@sherazdotnet2 жыл бұрын
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.
@Pazushh2 жыл бұрын
I think it shouldv'e been (Index-1)/2. while "/" rounds to bottom
@calviethang71392 жыл бұрын
You are right!
@SupunNimantha2 жыл бұрын
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.
@dennisfolz3522 жыл бұрын
@@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. ^^
@santjagocorkez10 ай бұрын
@@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.
@hammerain935 жыл бұрын
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
@leonardom.deoliveira44652 ай бұрын
Why not though?
@ggd123Ай бұрын
@@leonardom.deoliveira4465 The item at the end of the list still exists after you reassign items[0] so essentially you have a duplicate of the last item at the front.
@PsyKosh8 жыл бұрын
Possible error around 2:52 The diagram shows the parent as (index-2)/2, when it should be (index-1)/2
@g.o.46788 жыл бұрын
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.
@arvinsim8 жыл бұрын
Gbenga Ojo
@DimaKurguzov7 жыл бұрын
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.
@quangthang10d47 жыл бұрын
Yes I was gonna say the same thing!
@josevillegas27217 жыл бұрын
In python 2, / is integer division and it truncates the result so 5/2 = truncate(2.5) = 2
@harshitm64035 жыл бұрын
Storing the heap in the form of an array just blew my mind...so effective
@theinverteddonkey29613 жыл бұрын
it's really a tree in the form of a list of nodes
@typingcat2 жыл бұрын
Damn, if that blows your mind, your mind most be blown multiple times a day.
@davidlee5882 жыл бұрын
@@typingcat haha, i'm also been wondering why people easily got blown away by simply KZbin videos, it must be like an ejaculation moment for them. 😂
@vectoralphaSec2 жыл бұрын
@@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.
@hamzahkhan8782 жыл бұрын
what in the hell we were you thinking of if that blew your mind? lol
@m2rafik6 жыл бұрын
Most of coders strugles to use complex abstract data structures like heaps or graphs because they dont learn it from a concrete use case.
@sarvasvarora3 жыл бұрын
+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.
@stas49853 жыл бұрын
why the hell graphs or heaps complex???
@axea45543 жыл бұрын
@@stas4985 because they are more complex than a simple non-resizable array or a linked list
@harshwardhankoushik85155 жыл бұрын
The explanation with the code is amazzing !! loved it....seems that would work for me! Please continue with the good work
@johnkimura55857 жыл бұрын
Her keyboard clicks are the most satisfying sound
@RobsRobotChannel5 жыл бұрын
ASMR, wikipedia it.
@ivanleon61643 жыл бұрын
hate it.
@himanshusingh51183 жыл бұрын
😂😂😂 irritating
@sanjayvasnani9883 жыл бұрын
Nah. It seems as if her keyboard hates being used by her.
@NilakshMalpotra3 жыл бұрын
Agreed! Lovely sound
@NathanSowatskey9 ай бұрын
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.
@RachelWho2 жыл бұрын
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!
@adityamedhe2 жыл бұрын
that's not minor
@acymiranda4 жыл бұрын
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?
@dmitrybahtiarov35552 жыл бұрын
There is error at 2:56, parent is (index - 1 ) / 2 and not (index - 2) / 2
@CamdenBloke6 жыл бұрын
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
@xMercuryx562 жыл бұрын
that's not pro, that's just math ... lmfao
@octamodius5 жыл бұрын
Clean implementation. Clean explanation. Wonderful video! Thank you very much for taking the time to make this. I really needed it!
@WorklLife6 жыл бұрын
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!
@michaeldang81895 жыл бұрын
hasParent method should be simplified to: hasParent(int index) {return index > 0}
@randomrandom3165 жыл бұрын
Its quite clever
@brianspinos3 жыл бұрын
Nice!!!
@AyanSengupta176 жыл бұрын
It should be (index-1)/2 for the parent and not (index-2)/2. Please correct it.
@jkulkarn1003 жыл бұрын
At 10:31 , Parent should be Parent=(index-1) / 2
@anwarshaikh60238 жыл бұрын
Very nice explanation. Though including big O complexity of the operations would be great.
@BryanTidwell27 жыл бұрын
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
@damnstupidoldidiot87765 жыл бұрын
It should be O(nlog(n)).
@uusoft4 жыл бұрын
time complexity O(nlog(n)) space complexity O(1)
@drophy3 жыл бұрын
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.
@mvcds927 жыл бұрын
The video feels incomplete because it never explains what a heap is used for, though the data structure very well.
@jimmithfarrel89867 жыл бұрын
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.
@mvcds927 жыл бұрын
Yeah, I've googled it afterward, though it's kind of you helping me here, thanks!
@musicprod83666 жыл бұрын
Thank you : )
@xNajda6 жыл бұрын
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?
@sumitbhattacharya17206 жыл бұрын
go read a book then.
@Amolang9913 жыл бұрын
After you poll(), shouldn't you remove the element at `items[size - 1]`?
@karanbopche5 жыл бұрын
has parent method is wrong. it will return true for index 0 which is the first node and does not have a parent. it should be like private boolean hasParent(int index) {return index > 0; }
@jonasgrnbek71135 жыл бұрын
That butterfly keyboard sound 😕
@jimgetsjob95512 жыл бұрын
so simple to impliment, just paste these blocks of code and *BAM* it probably does stuff but good luck explaining it on an interview
@RagazzoKZ4 жыл бұрын
Very helpful video, but I don't like her voice
@dmitrybahtiarov35552 жыл бұрын
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.
@maheshnampoothirikv50806 жыл бұрын
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--;
@dishantsheth95925 жыл бұрын
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.
@AlexandruRepede7 жыл бұрын
this is useful for priority queues
@tamoorhamid5194 жыл бұрын
That's one application.
@jadanabil80444 жыл бұрын
@@tamoorhamid519 what are the other applications?
@tamoorhamid5194 жыл бұрын
@@jadanabil8044 They can be used to efficiently find the largest or smallest value in an array.
@mgeasley4 жыл бұрын
that's a lot of "head starts". smh
@tanveeralitapya72584 жыл бұрын
Yeah!
@kappamomondo10383 жыл бұрын
To be fair, watching her type out all of those methods would be incredibly mundane
@anirudhreddybasani35556 жыл бұрын
In getParentIndex() function if childIndex=0 then (childIndex-1)/2 would evaluate to 0 as integer division will be performed... so hasParent(int index) function would return true even if index=0 as getParentIndex() function would return 0...So I think hasParent() function is not working when index=0....Is it correct????
@imochurad5 жыл бұрын
It seems that your assumption is correct, however, you'll still gonna break from the while loop in heapifyUp() method b/c root is not bigger than itself. As a proper fix, one should check if the index passed into hasParent() method is 0. If it is -- return false.
@anujpancholi82934 жыл бұрын
hasParent or getParentIndex will not, and should not, work for index=0, since the root element itself is positioned at index 0, and by definition, it has no parent. You can include a check for this, but for the sake of simplicity, that check was not included here.
@aswinbeats7 жыл бұрын
int getParentIndex(int index) { return (index - 1)/2; } The above code will return 0 when index is 0. Thus, hasParent function for index 0 will return true. I think that getParentIndex should be as follows int getParentIndex(int index) { return (int) Math.ceil( ((double)index - 2)/2 ); } Thus, hasParent(0) will be false because -1 is less than 0. Did I miss anything?
@craigburkhart16166 жыл бұрын
I was thinking the same thing. Even at value of 1 you get 0/2 which is dividing by zero. I have been doing this on paper so i havent run your code but it does seem to address the issue i was puzzled by. Thanks for posting
@quantic72446 жыл бұрын
Noticed it too, if I'm not mistaken this issue is easily solved by changing the condition in the method hasParent: getParentIndex(index) > 0, instead of >=
@off_pudding4436 жыл бұрын
0/2 is not dividing by 0
@WASDsweden6 жыл бұрын
hasParent can simply be index != 0
@petersinsky91236 жыл бұрын
then it would return FALSE even in the case when the parent has index 0
@SuprStevn6 жыл бұрын
the function hasParent will return true for input index 0 (which has no parent). Unless I am missing something this is a bug. My code uses private boolean hasParent(int index) {return index >0;}
@shawnjackson75684 жыл бұрын
Space ooo yes this is a bug. Actually there are several bugs in here. Definitely the worst hacker rank video I’ve seen.
@dvvdsvsd7 жыл бұрын
I have final exam tomorrow, after this explanation, if this will be my pick, I know I'm safe. Amazing videos!
@utkarsh_1084 жыл бұрын
Best of luck
@ShermanSitter4 жыл бұрын
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! :)
@ShermanSitter4 жыл бұрын
@Chris Chu Learns ah shucks. thank you!
@kenansari3 жыл бұрын
how it was?
@Itskfx Жыл бұрын
Same, I'm terrible at heaps. These vids help a lot!
@alicianieto28224 жыл бұрын
The video is awesome and what I needed to know. Thank you!
@KelleyNielsenSalticidSoft7 жыл бұрын
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?
@RathodDharmin7 жыл бұрын
It's more readable and less code, but "else" gives you an idea of flow.
@mogomotsiseiphemo16815 жыл бұрын
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;
@ophir19827 жыл бұрын
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.
@nopenope84096 жыл бұрын
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
@LeaFox7 жыл бұрын
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.
@comosehaceyt3 жыл бұрын
Thank you :D
@kiaksarshirvanimoghaddam43543 жыл бұрын
I always had problems understanding heaps, but you made it so clear. Thank you so much ...
@AlexXPandian3 жыл бұрын
Best video explanation with code walkthrough showing how to answer the ubiquitous lazy interviewer question "Implement a Heap data structure".
@minjipack97275 жыл бұрын
1:54 said swap the value with the smaller child value, but the layer3 smaller value is 7 (7 < 9). Even in implementation part, it follows the same logic, so diagrams needs to be corrected as 20 should be under 9 I guess?
@stackingflow4 жыл бұрын
elements are inserted in left to right order and yeah the 20 is below 9 only
@ontimegrad70692 жыл бұрын
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?
@YuelengWang Жыл бұрын
I think the hasParent implementation is tedious, and btw, the index = 0 also return true for has parent. ( (0 -1) / 2 = 0, btw, so tennically the tutor's implementation is wrong, but since we use it this way: hasParent(index) && parent(index) > items[index] which does not make much hurt because parent(0) == items[0] and it will always return False here), you can just tell if index has parent by just index > 0, because every node has parent except the root which has index 0.
@DarthTofu25 жыл бұрын
Maybe I'm getting too far into the weeds, but how is this heap arranged? What are the times for number placement? Oh I were searching for the value 9, what rules would I use to run from the origin to that value?
@darwinnacionales135 жыл бұрын
I think the use of heap is to easily access either the minimum or the maximum value whenever you call the poll() method. If you need to be able to quickly search by value, you should be using BST.
@AMANDHOL-f7v2 ай бұрын
Quick question: Why do we have to compare with both 2:03 , left node and right node, because aren't left nodes intuitively supposed to be smaller than the right node?
@xXmayank.kumarXx4 ай бұрын
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)
@mattak774 жыл бұрын
private int getParentIndex(int childIndex) { return (childIndex - 1) / 2; } private bool hasParent(int index) { return getParentIndex(index) >= 0; } looking at these method, if I pass 0 to hasParent, it returns 0 because getParentIndex ==> (0-1)/2 returns 0 hasparent 0 >= 0 return true. But if an element is at index 0, it is root and no parent so the method should return false. What am I missing here?
@ijustsawthat4 ай бұрын
Do you know why Interviewers love questions about Trees, Graphs and Heaps ? Because to answer those, you have to write so much boilerplate, your interview time is gone. See how much she had to past in this just to start writing the actual solution.
@SicariusVIII5 жыл бұрын
Really have to appreciate the readability of the code a variables.
@trampflips1013 жыл бұрын
surely it's (index-1)/2, not (index-2)/2. The former would give 2 as parent for 5 and 6, whilst the latter would incorrectly give 1 as parent of 5.
@SpiritVector Жыл бұрын
My brain just short circuited, I think I might be stupid. So if to get to a child of an element you have to scale the index by two and then add one of two choices {1, 2}... but to do the reverse you have to (index -2) then divide that by 2? But what if the index is 1?
@felixg47857 жыл бұрын
I wish I had friends like her.
@arianazin54195 жыл бұрын
No please.
@AbdulmajedGamer4 жыл бұрын
I wish I had friends.
@ibrahimkassem7505 Жыл бұрын
There is an error in the code of getting the parent index, it must be "childIndex / 2 - 1" other wise it will be stuck in the root. or we can put in the while loop (hasParent(index) && index != 0
@listigertrex89232 жыл бұрын
Can someone explain me please why 50% of the internet says parent is (n-1) / 2 and the other 50% says its (n-2) / 2 in a Min Heap? For me when I do the calc (n-1) / 2 should be right.
@RobsRobotChannel5 жыл бұрын
At 6:45 it seems like she swaps the value of the parent with the index itself, rather than the value of the array at that index location. Should it not be: swap(getParentIndex(index), items[index]) on Line #56??????
@zaretix5 жыл бұрын
No. the swap method swaps the items at the two indices provided as arguments in swap().
@David_389k2 ай бұрын
Emotionally, we are thrilled to announce that the confirmation of your Sales Incentive payment has been processed.
@technowey3 жыл бұрын
Thanks you for this excellent video. It''s the best, most concise and straightforward, explanation of a heap that I've seen.
@BobBigWheels2 жыл бұрын
Simple explanation. I still don't understand why anyone would use a heap over a BST. Is it because it is much simpler to add and get the extreme value that is built for? What contexts is that useful?
@Allyourneedsmet2 жыл бұрын
If i said I understand anything, I would be lying... Shi
@H3000-v7i5 жыл бұрын
"Now what about removing the minimum element" Maybe rather start with removing an element in general. What are the rules here? These videos got potential and start out well, until you fuck them up! Either with mistakes in code, misuse of terminology, or forget to mention essential things. What a shame!
@aanchalsharma83623 жыл бұрын
Why do I relate to that node that is all empty inside! xD
@cicakmuhamed Жыл бұрын
At 1:38, did you mean "... we swap that value at the root with the last leaf node"? Because that is certainly not the same as swapping with the last element added. I find that confusing phrasing. Other than that, it's a great tutorial, thank you.
@Itskfx Жыл бұрын
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?
@exoexobtsbts25695 жыл бұрын
Worst thing you can do when teaching programming / computer science is continuously copying and pasting code out of nowhere. Terrible tutorial.
@whiskas-1 Жыл бұрын
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 )
@programmercouple3 жыл бұрын
This is the best explanation of Heap. Thanks 🙌🏻
@lolipopscandy627 жыл бұрын
How does this not have more views?? What a simple, and amazing explanation. Subscribed!!!
@palanisamymadakkannu43506 жыл бұрын
only entertainment videos ll get more views.. useful videos wont get..😊
@intrepidsouls6 жыл бұрын
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.
@blasttrash5 жыл бұрын
@@intrepidsouls I agree too. Her book is good though.
@thatoneuser86004 жыл бұрын
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.
@devinebug3 ай бұрын
What is the time and space complexity ? And what are the effective use cases for min/max heap?
@akhiljain16954 жыл бұрын
I was searching for something just like this. Awesome explanation of implementation of heap.
@Daniel___9v22 ай бұрын
By the unfortunate turn of events, a system error led to the transaction being sent to an invalid email address.
@lifewear.reseller3 жыл бұрын
Can someone explain me why don’t we just add 25 at the end of heap instead of deleting 10, because we just wanted to add new one not deleting the min one...?
@Bennettone5 жыл бұрын
Please fix error in parent index formula
@manuelhe463 жыл бұрын
The link to the coding interview tutorial is broken. It gets me a 404. I'm looking for the source code
@motivationalcomred2 жыл бұрын
3:28 getleftchildindex
@itsmewaqar7 жыл бұрын
Am I the only one who watch all of her videos on 0.75x speed ? Man, this girl speaks fast.
@IMC57762 жыл бұрын
Whats the intuition behind choosing the right child over the left child? Why do we choose the right child if it is less than the left child? A heap is not necessarily a binary search tree is it?
@carlosl582011 ай бұрын
I wish my data structures class at uni was as well explained as this video, my professor sucks
@pranavnyavanandi97102 жыл бұрын
Why do the heapify() methods need to be public ? Any reason a user might want to access them?
@abdulrashid10604 жыл бұрын
Secret of Learning Heaps; 1) Heaps = Arrays. (Start with Index 1) 2) Parent of Current Index = Current Index / 2 Where to Put new data? 3) Current Index Left Node = Current Index * 2 4) Current Index Right Node = (Current Index * 2) + 1
@devin69773 жыл бұрын
Why would you want the heapify methods to be public? Is there a need for them to be accessible outside of the class?
@this-is-bioman2 жыл бұрын
Why didn't you use Kotlin for the implementation? Java is so verbose :|
@GloriaPartin-o3e8 күн бұрын
Hall Elizabeth Thomas Karen Robinson Jose
@skylinefx0492 жыл бұрын
3:05 flashbang warning
@BeginningProgrammer5 жыл бұрын
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.
@beingyourself98246 жыл бұрын
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
@ShermanSitter4 жыл бұрын
at 1:50 if it gets swapped with the 'smaller' of the two, why does the 20 get swapped with the 9 instead of the 7?
@stackingflow4 жыл бұрын
+1
@gutenmorgan20633 жыл бұрын
i know you wrote this comment a while ago but I believe we do it that way because we have to go to the next available spot. If you write horizontally on all of the nodes starting from the root at 0, where she does in the video would be the next place you would go as if you wanted to add nodes, that would be the first place in terms of heaps. I hope this is helpful and that your figured it out!
@felica447411 ай бұрын
the index of node parent is (index-1)//2, not (index-2)/2.
@NickeManarin3 жыл бұрын
At @2:49, isn't parent = (index - 1) / 2 like the code uses ?
@DominicVictoria5 жыл бұрын
What overhead will you get from an array of class?
@nobodycaresmeself Жыл бұрын
her voice tone is like someone who is used to be reject candidates due to they cannot reverse a binary tree
@cameronswartzell1362 Жыл бұрын
Not a Java programmer so I don’t understand how “swap” works in the heapify up section at 6:45. She has swap(index1, index2)… but it’s not a method of any particular list or be or object, nor is she passing it a list. How would it know to swap the values of a particular list? Looking up docs it seems like this is just an error; the swap function is swap(list, index1, index2)
@gbh1998 Жыл бұрын
Hi Cameron, the answer is actually Object Oriented Programming. If you see the beginning of code, she has declared the array as what we call in Java an instance variable, which belongs to a class (also called members of a class), a blueprint/template of an object. So, with this, we can use our instance variable array in one of methods which are also members of a class. So, if the array is a member of a class, there is no point in sending it to one of the parameters in methods (in functional languages like C, they are functions) The swap method you have mentioned does not belong to a class, so we need to pass the array data structure to the method parameter. Hope I able to clear some doubts Check out Object Oriented Programming, more doubts will be cleared.
@gutenmorgan20633 жыл бұрын
5:24 - why are we removing the 10? what is the point of removing the minimum element?
4 жыл бұрын
A nice explanation, but I find the vocal fry unbearable to listen to.
@gauravmaithani47073 жыл бұрын
best vid ever... thanks McDowell.
@Amolang9913 жыл бұрын
what is the reason you set the helper methods as private and others for public?
@roman-berezkin2 ай бұрын
The best explanation of heaps ever, it got me first try.
@sandole972 жыл бұрын
Can I be wild and ask why Gayle has a Korean coding book in the intro?