Don't get confused by the left and right child index calculations here being different from a normal binary tree. Normally in a binary tree, left child index is parentIndex*2 + 1 and right child is parentIndex*2 +2. Here both of them are 1 less just because we're leaving index 0 blank so left becomes parentIndex*2, and right becomes parentIndex*2+1
@MichaelSalo4 жыл бұрын
I feel like this code could be clarified with some helper functions. Ex: getParent, getLeftChild, getRightChild
@SaranshDhingra3 жыл бұрын
Funnily, when I was practicing, I did create those functions myself :D But, the logic explanation seems good.
@miguelpetrarca55403 жыл бұрын
for real lol. I hate seeing cryptic unreadable code, hurts my soul and eyes
@miguelpetrarca55403 жыл бұрын
in your helper method, I would assume you would pass the index of a node for these methods, also if they dont have a left child or right, would method return null
@convolutionalnn25823 жыл бұрын
@@miguelpetrarca5540 I dont learn how to insert...How can i make Min Heap...I copy the code down...But i dont know how to insert etc etc
@TarasovFrontDev3 ай бұрын
The best video about the heap structure! Others one not even close. Keep up!
@carolinerobin42286 жыл бұрын
Super helpful, thanks Beau for all of your contributions. All of your Data Structure videos are fantastic. Been sharing them with my cohort!
@BeauCarnes6 жыл бұрын
Thanks!
@ebrahimmansour76064 жыл бұрын
This is wrong, because if there is an element in the left, then we need to check if (this.heap[left] == undefined || this.heap[right] == undefined) { break; }
@codingliteracy192 жыл бұрын
Why do you have to sacrifice index zero? Since most arrays always start at zero, we can then use the following formulas: Left child: 2n+1 Right child: 2n+2
@ironrose63 жыл бұрын
While I appreciate the info, why did he choose to show the diagram for a max heap and then walk through the code of a min heap? He even showed us that he has the code for a min heap already there, so why show one thing and explain how to build the opposite? Even more nonsensical, he leaves the diagram of the max heap side by side the whole time he's walking through the code of the min heap. Anyone who wants a visual representation of the min heap while he explains the code has to ignore the diagram displayed side by side with the code.
@_7__7162 жыл бұрын
Destructuring syntax creates new arrays and increases space complexity.
@princeofexcess Жыл бұрын
it creates new arrays but it doesnt increase space complexity as space complexity only cares about n. O(n+2) = O(n) now this might still matter if youre coding for a chip but not on an interview.
@ranesh2376 жыл бұрын
shouldn't we replace the || with and && here: if(heap[left] == undefined || heap[right] == undefined){ break; } be this instead: if(heap[left] == undefined && heap[right] == undefined){ break; } because we still want to swap even if the parent has only "one" child.
@Ford-ju9yr6 ай бұрын
Yes, but then you also will need to change line 43 to: If( (heap[left]
@allovince22575 жыл бұрын
demo code is wrong! if heap is 1,2,3,4,5 run heap.remove() will get 2,5,3,4 but correct should be 2,4,3,5
@41186pr5 жыл бұрын
culprit is condition checking undefined for left and right in remove function. instead of OR we should have AND
@michaeljiang10025 жыл бұрын
lol havent run the program to check it, but yeah
@wayneli38905 жыл бұрын
if (heap[right] === undefined) { if (heap[i] >= heap[left]) { [heap[i], heap[left]] = [heap[left], heap[i]]; } break; } if (heap[left] === undefined) { break; }
@harrisonxm7 жыл бұрын
Thanks for making this video!
@eywahbabam4 жыл бұрын
Thank you Beau. My question is; when you sort the heap, you also remove everything in the actual heap. Is this expected? I mean, if I sort it and then insert another element, the heap will have only 2 elements; the null and the last thing I added.
@eywahbabam4 жыл бұрын
Hence, I changed it this way: this.sort = function(){ let tempHeap = [ ...heap ] ; let result= [ ] ; while( heap.length > 1 ){ result.push(this.remove( )) ; } heap = tempHeap ; return result; }
@ctdr11910 ай бұрын
Super helpful
@Tyrowo2 жыл бұрын
at 10:38, in the remove function you use .splice(heap.length-1); to splice off the last element of our array.. is it faster to use splice instead of a .pop(); there?
@广东靓仔6 жыл бұрын
"this._heap[left] === undefined || this.heap[right] === undefined" I think || sign should be && sign and other logic should be changed respectively
we'll, we don't need to check that both is undefined, if we know that the left one is undefined then we know for sure that the right one is also empty. But if the left one is not undefined we can still run the look
@prakashavvaru69977 жыл бұрын
what's the use of if(idx>=1) statement as checking is already done on while statement.(In min heap insert program)
@ebrahimmansour76064 жыл бұрын
There is no need to this condition, because after swapping, if the index if less than 2 the loop will break. consider the condition of (idx >= 1) is false, what will happen?? infinite looooop
@goadler8330 Жыл бұрын
Yes exactly I was thinking the same. 😅
@JSDev7762 жыл бұрын
why would you write "heap.splice(heap.length - 1)" when you can do the same thing with heap.pop() ???
@dd888164 жыл бұрын
nice video!
@michaeljiang10025 жыл бұрын
if we cut off the last element on line 57, we would be left with just the array with one element in is which is null, then why are we cutting it off?
@mahmoudezzat4176 Жыл бұрын
messy remove function makes it very hard to understand
@muhammedsami30585 жыл бұрын
thank you for your help but your insert function does not work properly
@maxl.56074 жыл бұрын
My I ask what is the draw tool?
@gidmanone7 жыл бұрын
my head hurts watching this
@ndurocher856 жыл бұрын
How do we add to the heap?
@billwindsor42246 жыл бұрын
+ndurocher85 You add a node to the heap by finding the first empty node at the bottom of the heap, and then ordering the heap nodes by successive comparisons to compare and swap nodes. See this tutorial with good animations: kzbin.info/www/bejne/qmGmommqi7OFeKM
@michaeljiang10025 жыл бұрын
Yo dude how should i run this? in node?
@snoudoubts17452 жыл бұрын
0:00 was enough to make me pause the video and search for another video
@StaceyWilsonlosangeles3 жыл бұрын
Although, this works... There is a better way to implement a min or max heap.
@travholt7 жыл бұрын
I'm sorry, but this video is not very helpful. There's not one word about WHY heaps are used, so I'm not given any incentive to learn HOW.
@BeauCarnes7 жыл бұрын
One of the main use cases is discussed later in the video. It is used in heapsort which is one of the fastest sorting algorithms. I guess I could have put that toward the beginning instead of the end. :)
@travholt7 жыл бұрын
Okay, a few words about WHY, then. :-) But yes, I definitely think mentioning that (or even better: showing a practical example) in the beginning would help.
@jtnix6 жыл бұрын
pretty much any social site with a ranking system is using a max and/or min heap sort to manage their scoreboard rankings. think of stackoverflow's or reddit's contributor ranking systems, which likely use optimized, object store backed max heaps to manage the user ranks.