This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Heap Sort Solution" Lesson
[00:00:00]
>> Brian Holt: Okay, so let's go ahead and,
>> Brian Holt: Take a look at how to do this.
>> Brian Holt: This requires about 50 lines of code.
>> Brian Holt: So you're gonna create a function here called, so the snapshot thing is how I'm able to show the visualization there, so you can just basically ignore it.
[00:00:41]
>> Brian Holt: And I gave you here, basically, the guts. So you're gonna have a createMaxHeap function, a heapify function, and then the heapSort, which is intern going to call both of those functions internally from heapSort. So let's start with the create max-heap, it's a pretty simple one. All you're gonna do is you're gonna start with a for loop and say let i is 0.
[00:01:15]
>> Brian Holt: Sorry, i = Math.floor,
>> Brian Holt: Of array.length divided by 2, and i is greater than or equal to 0, and then i minus minus, right? So you're gonna start from the middle of the array and go backwards.
>> Brian Holt: Then you're just gonna call heapify on array, i, and array length.
[00:01:50]
>> Brian Holt: And you're gonna return to the array.
>> Brian Holt: So the array, right, that makes sense. The index of where we currently are, that probably makes sense as well, cuz we're gonna be heapifying. And then we have to give it the heap size, because remember when we're doing the heap sort part of it, the heap size makes a difference of where and how far it can go.
[00:02:13] And you don't want it to go to the end of the array when we're doing heap sort cuz otherwise it would mess up the sorted part of the list. We wanna progressively make our heap smaller and smaller, which is why we're passing in heap size.
>> Brian Holt: So let's take a look at what heapify looks like.
[00:02:32]
>> Brian Holt: So here you're going to do,
>> Brian Holt: We'll call it at the end,
>> Brian Holt: Const left = 2. So this is gonna be the left child times index +1. Const right = 2 times index + 2.
>> Brian Holt: So you're gonna say let largest ValueIndex = index.
>> Brian Holt: Then here I'm just gonna ask, if the left child bigger?
[00:03:10] Is the right child bigger? And if one of them was bigger, then I'll swap them. If one of them's not bigger, then I'll leave it, right? So I'm going to ask if heapSize, that is, yeah, yeah, yeah. So if heapSize is like out of bounds that I'm not gonna check it, which is what you're doing here, then you're gonna say end array.
[00:03:50]
>> Brian Holt: Array largest value index is less than array of left, right? So,
>> Brian Holt: So the first time the largest value, you could just as easily put index here as well. I just think it's a little bit easier to read this way. So if left is greater than the parent, right?
[00:04:25] The index, then we're gonna swap the left child in. So largestValueIndex = left, if(heapSize
>> Brian Holt: If right is in bounds, then you're gonna say and array largestValueIndex. Array right.
>> Brian Holt: Then you're gonna say largestValueIndex = right. Okay? So now I know for a fact that the largest value index is definitely contained in this one.
[00:05:08] It's either the parent, the left child, or the right child, after doing these two comparisons. Then I'm gonna say if the largestValueIndex is not equal to, index, right? So If either the left child or the right child is bigger then we have to do a swap. If it is the parent, then you just leave it.
[00:05:30] Cool, do you follow?
>> Brian Holt: Okay, then what we're gonna do is just do a swap, right? const temp = array[index]; array[index] = array[largestValueIndex].
>> Brian Holt: Then, you're just gonna say array[largestValueIndex] is gonna be assigned temp.
>> Brian Holt: And then at this point, if you remember, if we do heapify something, we have to heapify the child that's swapped.
[00:06:10] Because we have to guarantee that order still maintains further down the tree as well. So only if one of the swaps happens, we're gonna call it heapify on the array at the largestValueIndex. And heapSize,
>> Brian Holt: Does that make sense?
>> Student1: Are you keeping track of the heapSize, because you're slowly making it smaller until the whole thing is sorted?
[00:06:36]
>> Brian Holt: Exactly.
>> Student1: Okay.
>> Brian Holt: So the heap continues to get smaller and smaller and smaller. If I included the entire array every single time, I would swap something to the end, and then it would just get moved back up to the front.
>> Student1: Okay, you would never sort it.
[00:06:46]
>> Brian Holt: Yeah.
>> Student1: Okay.
>> Brian Holt: But that's astute.
>> Student2: I think you have the wrong greater and less-than on the right check.
>> Brian Holt: I don't think so.
>> Student2: Cuz you're saying the current one is greater than the right one, but you're assigning right to the current or to the largest.
[00:07:11]
>> Brian Holt: Right. No, you're right, here. I was looking at this one.
>> Student2: Yeah.
>> Brian Holt: You were correct, thank you.
>> Brian Holt: Okay, so now I have heapify. I have createMaxHeap. So definitely when I call createMaxHeap, at the end of that whole process I will have a valid MaxHeap, okay?
[00:07:36] So what I'm gonna do here in heapSort the first thing I'm going to do is say that array is assigned createMaxHeap of the array. So now array is an assorted max heap. Then I'm gonna have this temp variable and I'm gonna say for(let i = 0,
>> Brian Holt: Sorry let i = array.length -1, cuz you can you don't have to start, yeah you don't have to do the last one cuz by that point it will be sorted.
[00:08:14] i > 0 and i --.
>> Brian Holt: Okay? So what you're gonna do is you're gonna say temp go to the end.
>> Brian Holt: Or rather temp is going to be the first item. array
[0] is going to become array at i, right? Because we're going to be swapping these.
>> Brian Holt: array i is going to be assigned temp, heapSize--, and then you're gonna call heapify with the array, 0, right?
[00:08:59] Cuz heapify, you're always starting from the beginning, right, because that's the one you swapped in. And heapSize which is progressively getting smaller each time that you do it.
>> Student2: Where are you setting heapSize?
>> Brian Holt: Right here, the -- previous to it.
>> Brian Holt: And I didn't do it up here, no you're right, up here, let heapSize start as the array.length.
[00:09:36]
>> Brian Holt: So again, just to walk you through it. Treat your variables up here, heapSize is going to be the entire array the first time. We're going to make the array a max heap, which we do here by calling heapify on every individual item in the array, right? Or rather, make sure that every item gets affected by a heapify, which is why you start in the middle.
[00:10:00] Because remember, it's 2n plus 1, which means if I'm heapifying from the middle, it's going to be looking at the end of the array. Which is why that works. Heapify just goes through, and just makes sure that the parent is always larger than the children, that's the entire gist of that.
[00:10:15] If not, it sweeps, it swaps them and then it makes sure to call heapify on the children that it swapped. Only the children that it swapped. Once we've done that we have a max heap and we can go from there. And just be swapping out items and calling heapify on the zero element.
[00:10:34] So, hopefully, that gives us a sorted array. It does.
>> Brian Holt: How do you feel about heaps? Does that make some sense? Cool. It's a little difficult to explain this a little, It's not terribly concrete until you actually see it. But yeah, hopefully that explains it. If you wanna see what it looks like when you do a lot more numbers, you can just swap these tests out, run it.
[00:11:04]
>> Brian Holt: And you can see that the nice pretty colored gradients.