Data Structures: Heaps

Поділитися
Вставка
  • Опубліковано 10 січ 2025

КОМЕНТАРІ • 463

  • @WorklLife
    @WorklLife 7 років тому +91

    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!

  • @harshitm6403
    @harshitm6403 5 років тому +309

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

    • @theinverteddonkey2961
      @theinverteddonkey2961 3 роки тому +11

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

    • @typingcat
      @typingcat 2 роки тому +21

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

    • @davidlee588
      @davidlee588 2 роки тому

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

    • @vectoralphaSec
      @vectoralphaSec 2 роки тому +65

      @@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
      @hamzahkhan878 2 роки тому +3

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

  • @sherazdotnet
    @sherazdotnet 3 роки тому +127

    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
      @Pazushh 2 роки тому +9

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

    • @calviethang7139
      @calviethang7139 2 роки тому

      You are right!

    • @SupunNimantha
      @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
      @dennisfolz352 2 роки тому +1

      @@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
      @santjagocorkez Рік тому +2

      @@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.

  • @hammerain93
    @hammerain93 5 років тому +69

    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.deoliveira4465
      @leonardom.deoliveira4465 6 місяців тому

      Why not though?

    • @ggd123
      @ggd123 5 місяців тому

      @@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.

  • @PsyKosh
    @PsyKosh 8 років тому +587

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

    • @g.o.4678
      @g.o.4678 8 років тому +36

      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
      @arvinsim 8 років тому

      Gbenga Ojo

    • @DimaKurguzov
      @DimaKurguzov 8 років тому +56

      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
      @quangthang10d4 7 років тому +5

      Yes I was gonna say the same thing!

    • @josevillegas2721
      @josevillegas2721 7 років тому +6

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

  • @Saztog1425
    @Saztog1425 3 роки тому +115

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

    • @AlanD20
      @AlanD20 3 роки тому +6

      EXACTLYYYY 😂😂😂

  • @octamodius
    @octamodius 6 років тому +26

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

  • @CamdenBloke
    @CamdenBloke 6 років тому +18

    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
      @xMercuryx56 2 роки тому +10

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

  • @NathanSowatskey
    @NathanSowatskey Рік тому +3

    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.

  • @harshwardhankoushik8515
    @harshwardhankoushik8515 5 років тому +40

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

  • @ophir1982
    @ophir1982 7 років тому +12

    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
      @nopenope8409 6 років тому +4

      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

  • @MrJakson112
    @MrJakson112 2 роки тому

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

  • @m2rafik
    @m2rafik 6 років тому +86

    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
      @sarvasvarora 4 роки тому +5

      +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
      @stas4985 3 роки тому

      why the hell graphs or heaps complex???

    • @axea4554
      @axea4554 3 роки тому

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

  • @johnkimura5585
    @johnkimura5585 7 років тому +164

    Her keyboard clicks are the most satisfying sound

  • @LeaFox
    @LeaFox 7 років тому +3

    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.

  • @mvcds92
    @mvcds92 7 років тому +170

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

    • @jimmithfarrel8986
      @jimmithfarrel8986 7 років тому +99

      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
      @mvcds92 7 років тому +28

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

    • @musicprod8366
      @musicprod8366 7 років тому +3

      Thank you : )

    • @xNajda
      @xNajda 6 років тому +3

      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
      @sumitbhattacharya1720 6 років тому

      go read a book then.

  • @JOJOSHgaming7514
    @JOJOSHgaming7514 4 роки тому

    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#.

  • @AlexXPandian
    @AlexXPandian 4 роки тому +1

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

  • @guadalupevictoriamartinez4537
    @guadalupevictoriamartinez4537 3 роки тому

    I forgot this channel existed. It saved me once again

  • @BeginningProgrammer
    @BeginningProgrammer 5 років тому +3

    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.

  • @roman-berezkin
    @roman-berezkin 5 місяців тому

    The best explanation of heaps ever, it got me first try.

  • @dvvdsvsd
    @dvvdsvsd 8 років тому +32

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

    • @utkarsh_108
      @utkarsh_108 4 роки тому +1

      Best of luck

    • @ShermanSitter
      @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
      @ShermanSitter 4 роки тому

      @Chris Chu Learns ah shucks. thank you!

    • @kenansari
      @kenansari 4 роки тому +2

      how it was?

    • @Itskfx
      @Itskfx 2 роки тому

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

  • @dmitrybahtiarov3555
    @dmitrybahtiarov3555 2 роки тому +4

    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
      @Itskfx 2 роки тому

      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.

  • @kiaksarshirvanimoghaddam4354
    @kiaksarshirvanimoghaddam4354 4 роки тому +4

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

  • @murnoth
    @murnoth 2 роки тому

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

  • @michaeldang8189
    @michaeldang8189 6 років тому +13

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

  • @KelleyNielsenSalticidSoft
    @KelleyNielsenSalticidSoft 7 років тому +5

    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?

    • @RathodDharmin
      @RathodDharmin 7 років тому +2

      It's more readable and less code, but "else" gives you an idea of flow.

    • @mogomotsiseiphemo1681
      @mogomotsiseiphemo1681 6 років тому

      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;

  • @lolipopscandy62
    @lolipopscandy62 8 років тому +48

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

    • @palanisamymadakkannu4350
      @palanisamymadakkannu4350 7 років тому +3

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

    • @intrepidsouls
      @intrepidsouls 6 років тому +2

      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
      @blasttrash 6 років тому

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

    • @thatoneuser8600
      @thatoneuser8600 4 роки тому +1

      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.

  • @technowey
    @technowey 3 роки тому +3

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

  • @anwarshaikh6023
    @anwarshaikh6023 8 років тому +62

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

    • @BryanTidwell2
      @BryanTidwell2 8 років тому +12

      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
      @damnstupidoldidiot8776 5 років тому

      It should be O(nlog(n)).

    • @uusoft
      @uusoft 4 роки тому

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

    • @drophy
      @drophy 4 роки тому +2

      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.

  • @minjipack9727
    @minjipack9727 5 років тому +2

    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?

    • @stackingflow
      @stackingflow 4 роки тому

      elements are inserted in left to right order and yeah the 20 is below 9 only

  • @VideosOfEarth
    @VideosOfEarth 5 років тому +1

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

  • @RachelWho
    @RachelWho 3 роки тому +2

    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!

  • @Nellak2011
    @Nellak2011 2 місяці тому

    I finally understand, just in time for my first Technical Interview tomorrow.

  • @whiskas-1
    @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 )

  • @xXmayank.kumarXx
    @xXmayank.kumarXx 8 місяців тому

    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)

  • @supportteam2007
    @supportteam2007 8 років тому +1

    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
      @bigbangind 7 років тому

      I don't think so

    • @supportteam2007
      @supportteam2007 7 років тому

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

  • @Thunder117
    @Thunder117 3 роки тому

    This is the most helpful code video i have ever seen

  • @AMANDHOL-f7v
    @AMANDHOL-f7v 5 місяців тому

    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?

  • @AlexandruRepede
    @AlexandruRepede 8 років тому +90

    this is useful for priority queues

    • @tamoorhamid519
      @tamoorhamid519 4 роки тому +1

      That's one application.

    • @jadanabil8044
      @jadanabil8044 4 роки тому +1

      @@tamoorhamid519 what are the other applications?

    • @tamoorhamid519
      @tamoorhamid519 4 роки тому

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

  • @jkulkarn100
    @jkulkarn100 3 роки тому +1

    At 10:31 , Parent should be Parent=(index-1) / 2

  • @cicakmuhamed
    @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.

  • @RobsRobotChannel
    @RobsRobotChannel 5 років тому +1

    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??????

    • @zaretix
      @zaretix 5 років тому

      No. the swap method swaps the items at the two indices provided as arguments in swap().

  • @sachinmagdum
    @sachinmagdum 3 роки тому

    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.

  • @enkhboldochirbat3578
    @enkhboldochirbat3578 4 роки тому

    This is best explanation of BST on basic concepts.

  • @acymiranda
    @acymiranda 4 роки тому +2

    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
      @dmitrybahtiarov3555 2 роки тому

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

  • @Amolang991
    @Amolang991 3 роки тому +1

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

  • @yourManLan
    @yourManLan 6 років тому

    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

  • @programmercouple
    @programmercouple 3 роки тому +1

    This is the best explanation of Heap.
    Thanks 🙌🏻

  • @cameronswartzell1362
    @cameronswartzell1362 2 роки тому

    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
      @gbh1998 2 роки тому

      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.

  • @akhiljain1695
    @akhiljain1695 4 роки тому +4

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

  • @ShermanSitter
    @ShermanSitter 4 роки тому +1

    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?

    • @stackingflow
      @stackingflow 4 роки тому

      +1

    • @gutenmorgan2063
      @gutenmorgan2063 3 роки тому +1

      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!

  • @satyam_dey
    @satyam_dey 2 роки тому

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

  • @maheshnampoothirikv5080
    @maheshnampoothirikv5080 6 років тому +3

    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
      @dishantsheth9592 5 років тому +3

      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.

  • @NickeManarin
    @NickeManarin 3 роки тому

    At @2:49, isn't parent = (index - 1) / 2 like the code uses ?

  • @beingyourself9824
    @beingyourself9824 6 років тому +1

    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

  • @motivationalcomred
    @motivationalcomred 2 роки тому

    3:28 getleftchildindex

  • @nyahhbinghi
    @nyahhbinghi 2 роки тому

    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?

  • @illiaharkusha9859
    @illiaharkusha9859 3 роки тому

    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?

  • @gutenmorgan2063
    @gutenmorgan2063 3 роки тому

    5:24 - why are we removing the 10? what is the point of removing the minimum element?

  • @lilypad5182
    @lilypad5182 2 роки тому +1

    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

  • @eddiet279
    @eddiet279 7 років тому

    Very clear. Even more clear than the book actually.

  • @johnnybravo964
    @johnnybravo964 Рік тому

    Sorted linked list is better than a heap! A sorted linked list would have better time complexity since removing the biggest or smallest element wouldn't require the entire list to be restructured. A bit more memory is required though for pointers.

  • @adityachawla2163
    @adityachawla2163 5 років тому +1

    At 2:51 How do you know that the element at the top will still be minimum after insertion?

    • @shawnjackson7568
      @shawnjackson7568 4 роки тому

      Aditya Chawla what do you mean? The algorithm for addition doesn’t change based on the underlying storage tool

  • @BobBigWheels
    @BobBigWheels 2 роки тому

    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?

  • @SuprStevn
    @SuprStevn 6 років тому +2

    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;}

    • @shawnjackson7568
      @shawnjackson7568 4 роки тому

      Space ooo yes this is a bug. Actually there are several bugs in here. Definitely the worst hacker rank video I’ve seen.

  • @rock53355
    @rock53355 3 роки тому

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

  • @SicariusVIII
    @SicariusVIII 6 років тому +2

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

  • @ravirajawasthi
    @ravirajawasthi 6 років тому +2

    Error at 1:56 on the second level of heap 20 should be exchanged by 7 instead of 9

  • @tritrinh568
    @tritrinh568 7 років тому +1

    Didn't know HackerRank has itself a UA-cam channel. Subscribed! :)

  • @satishchandra6623
    @satishchandra6623 7 років тому

    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?

    • @abhinav_agnihotry
      @abhinav_agnihotry 7 років тому +1

      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.

  • @aswinbeats
    @aswinbeats 7 років тому +4

    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?

    • @craigburkhart1616
      @craigburkhart1616 7 років тому

      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

    • @quantic7244
      @quantic7244 7 років тому

      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_pudding443
      @off_pudding443 7 років тому +3

      0/2 is not dividing by 0

    • @WASDsweden
      @WASDsweden 6 років тому

      hasParent can simply be index != 0

    • @petersinsky9123
      @petersinsky9123 6 років тому

      then it would return FALSE even in the case when the parent has index 0

  • @anirudhreddybasani3555
    @anirudhreddybasani3555 6 років тому +4

    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????

    • @imochurad
      @imochurad 6 років тому

      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.

    • @anujpancholi8293
      @anujpancholi8293 4 роки тому

      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.

  • @aaryadeshpande1621
    @aaryadeshpande1621 2 роки тому

    5:54: Why do we add size before heapifyUp(); why not after?

    • @gbh1998
      @gbh1998 2 роки тому

      At 3:04, check the class declaration, the instance variable size is initialised to zero. Now consider the first scenario, where absolutely the array is empty, at line 48 the element is inserted, after which the size is increased from zero to one. Now heapifyUp() is called, there we are trying to access the last element as size - 1, which will be 1- 1 which is 0, the first element.
      Now think if you don't increase it, and call the heapifyUp method. The same Operation will return -1, which will give you IndexOutOfBoundsException.
      This is the reason!
      Although in Python, you can access negative indices, but still the logic will be wrong by not increasing the size. (As the size variable is dynamically increasing upto capacity variable)

  • @SavageScientist
    @SavageScientist 3 роки тому

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

  • @ontimegrad7069
    @ontimegrad7069 3 роки тому +1

    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?

  • @AshfaqAhmed05
    @AshfaqAhmed05 2 роки тому

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

  • @chaptersdiversified2940
    @chaptersdiversified2940 3 роки тому

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

  • @Lisa-kk6go
    @Lisa-kk6go 6 років тому

    I saw an error at 3:04 . Parent is (index-1)/2 instead of (index-2)/2

  • @alicianieto2822
    @alicianieto2822 4 роки тому +6

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

  • @AyanSengupta17
    @AyanSengupta17 6 років тому +6

    It should be (index-1)/2 for the parent and not (index-2)/2. Please correct it.

  • @IMC5776
    @IMC5776 2 роки тому

    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?

  • @tomyang7788
    @tomyang7788 7 років тому +1

    where is the code that actually deletes the number 25 at the bottom at 9:22 ?

    • @derekfulginiti399
      @derekfulginiti399 7 років тому +2

      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.

  • @devinebug
    @devinebug 6 місяців тому

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

  • @farithd2042
    @farithd2042 3 роки тому

    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

  • @DarthTofu2
    @DarthTofu2 5 років тому +1

    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?

    • @darwinnacionales13
      @darwinnacionales13 5 років тому

      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.

  • @David_389k
    @David_389k 5 місяців тому

    Emotionally, we are thrilled to announce that the confirmation of your Sales Incentive payment has been processed.

  • @jimgetsjob9551
    @jimgetsjob9551 2 роки тому +1

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

  • @devin6977
    @devin6977 3 роки тому

    Why would you want the heapify methods to be public? Is there a need for them to be accessible outside of the class?

  • @ManuelRochaCR
    @ManuelRochaCR 7 років тому

    I completely ignored about heaps. Nice explanation. Thanks!

  • @conandev3710
    @conandev3710 3 роки тому

    Thank you very much for the video.
    At 1:53, wouldn't it be better to swap it with the greatest of the two children? This way, we would have less probability to call the BubbleDown function along the way down, and thus become more efficient?

    • @druhu4590
      @druhu4590 3 роки тому

      but then the greater of the two children would now be the parent of something smaller than it, which is bad for a min Heap

  • @Nickel80
    @Nickel80 5 років тому +1

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

    • @wotizit
      @wotizit 4 роки тому

      should O(nlogn) worst case

  • @gauravmaithani4707
    @gauravmaithani4707 4 роки тому +1

    best vid ever... thanks McDowell.

  • @manojkanduri1823
    @manojkanduri1823 5 років тому

    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.

  • @hammerain93
    @hammerain93 5 років тому

    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!

  • @abhinavtiwari3284
    @abhinavtiwari3284 3 роки тому

    One small confusion. On line 9, in getParentIndex.....if childIndex is zero, then it will return (0-1)/2 which is zero. Parent of 0th index should not be 0. Please correct me if I am misinterpreting.

  • @DanielSincAlexandru
    @DanielSincAlexandru 4 роки тому

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

  • @raivatshah7847
    @raivatshah7847 5 років тому

    Possible abstraction-breaking at 4:23? Instead of returning items[0], could we use one of the public methods to return the same thing. I think it is breaking abstraction because it is accessing the private items array directly and returning the 1st element at index 0.

  • @tomyang7788
    @tomyang7788 7 років тому

    at 9:24 why did u choose to replace the 10 with the 25 and not the 17 ?

    • @derekfulginiti399
      @derekfulginiti399 7 років тому

      The "extractMin()" function that she refers to will always replace the root item with the last item in the array, in this case 25. Then it will heapifyDown() the new root item until the Heap properties are restored.

  • @mariezhang6818
    @mariezhang6818 4 роки тому

    Should didn't heapifyUp() compare both item[index] vs parent and item[index] vs parent.anotherChild to make sure the smallest become the new parent?