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
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
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; }
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?
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.
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.
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.
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
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.
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
+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: ruclips.net/video/t0Cq6tVNRBA/видео.html
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
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. :)
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.
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.
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
The best video about the heap structure! Others one not even close. Keep up!
Super helpful, thanks Beau for all of your contributions. All of your Data Structure videos are fantastic. Been sharing them with my cohort!
Thanks!
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
I feel like this code could be clarified with some helper functions. Ex: getParent, getLeftChild, getRightChild
Funnily, when I was practicing, I did create those functions myself :D But, the logic explanation seems good.
for real lol. I hate seeing cryptic unreadable code, hurts my soul and eyes
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
@@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
Thanks for making this video!
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;
}
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?
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.
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.
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;
}
Super helpful
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.
Yes, but then you also will need to change line 43 to:
If( (heap[left]
0:00 was enough to make me pause the video and search for another video
nice video!
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
thank you for your help but your insert function does not work properly
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?
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
culprit is condition checking undefined for left and right in remove function. instead of OR we should have AND
lol havent run the program to check it, but yeah
if (heap[right] === undefined) {
if (heap[i] >= heap[left]) {
[heap[i], heap[left]] = [heap[left], heap[i]];
}
break;
}
if (heap[left] === undefined) {
break;
}
My I ask what is the draw tool?
Destructuring syntax creates new arrays and increases space complexity.
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.
Yo dude how should i run this? in node?
what's the use of if(idx>=1) statement as checking is already done on while statement.(In min heap insert program)
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
Yes exactly I was thinking the same. 😅
my head hurts watching this
How do we add to the heap?
+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: ruclips.net/video/t0Cq6tVNRBA/видео.html
why would you write "heap.splice(heap.length - 1)" when you can do the same thing with heap.pop() ???
"this._heap[left] === undefined || this.heap[right] === undefined"
I think || sign should be && sign and other logic should be changed respectively
if (heap[right] === undefined || heap[left] > | < heap[right]) ..
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
messy remove function makes it very hard to understand
Although, this works... There is a better way to implement a min or max heap.
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.
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. :)
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.
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.