Heap Sort Practice

[00:00:00]
>> So let's go ahead, and go set this up. We're gonna pop over to our code sandbox, that's fine. We're gonna go into heapsort. Okay, and then I gave you, you do not have to do it this way. I'm just trying to kind of help you along and give you the skeleton of how to do this.

[00:00:32]
I suggest you break this down into three functions, right, heapsort which is actually what's gonna be called. Then this function called heapify, which is just my favorite word in this entire course is it there's some good words in this course but heapify is a pretty good one. This is actually that process that's gonna check.

[00:00:51]
Okay, am I in the right place? Am I bigger than my children? Do I need to swap these? So that would take in the array, the index and the heap size and then you can figure out where you need to move things. And then createMaxHeap. This is basically going to be the function that just loops over your array and calls heapify in reverse order.

[00:01:15]
I actually even gave you here in the course notes, the loop, right, this is the loop that you're going to write of what to loop over. This is the for loop that you're going to put inside of your createMaxHeap. The reason I gave this to this because it took me way too long to figure this out myself.

[00:01:32]
I didn't want you to have to struggle on something that didn't seem like it was that useful too. Cool, and then you'll put that here inside of createMaxHeap. And then I wrote one more function here just called swapPlace. Just takes a index1, index2 and an array. And all this does is swap two items in an array, because you have to do so much swapping in here.

[00:02:08]
It's nice to just have kind of a helper function that does it for you. Again, I'm just kind of throwing out ideas here. You're welcome to do however, we're where you see fit. There's not much recursion in here, the only place that you're gonna use a little bit of recursion is inside of heapify.

[00:02:25]
So heapify does call itself sometimes Let's hop into this heapsort function. I don't know why I feel like I have to like extra emphasize the P in heap,but every time it says heap sort, I don't know. Anyway, array=createMaxHeap(array). Okay, so we're gonna go into it. We'll create a MaxHeap down here and this function down here, but after that point we'll have a MaxHeap.

[00:03:03]
Then all we're gonna do is we're gonna say let i=array.length-1. So we're gonna start from the back, right? I is greater than 0. Obviously we don't need a heapify on 0 with time, right, because once everything has been swapped, inherently the last number or the first number, the 0 with index will be the smallest item in the array.

[00:03:30]
Hence the greater than and not greater than or equal, and then i- -. Okay, so we're going backwards over the array. All we're gonna do is we're going to call swap place, 0, i, an array. And then all we're gonna do is say heapify(array 0, i). Okay, so this is the core sorting part of the algorithm right here.

[00:04:02]
Create a MaxHeap, then just work backwards over the array, swap places, and then call heapify, that's it. CreateMaxHeap, let's do swap place first because that's what I have my notes first. Pretty simple, you're just gonna say, let temp = array[index 1] array[index 1] is signed array[index2]. Array[index2] is assigned temp return array.

[00:04:51]
Okay, that's swap place. Let's go down and do, CreateMaxHeap, this one. Here we're gonna say, for and we're just going to do that, for loop that I was talking about let i = math.floor, (array.length/2)-1. I is greater than or equal to 0, i--. Kind of a bit of a mouthful there.

[00:05:32]
Okay, and then we just call heapify on array, i and then array.length. So you might be asking, what is this length? This heapSize, right, is because as we're sorting our array, the length of our array kind of changes, right. Because as we're doing this part. This i's was changing, right?

[00:05:59]
So that everything before the i in here is sorted. So we want to exclude those from our heapify, right? So going back to here, basically when we're starting arriving to here, right? We want to kind of remove these from our heap. These two are no longer children in our heap, right?

[00:06:19]
So that's what that array size of the heap size represents, as we want to say everything in here is the unsorted heap. Everything over here is the sorted part of the array. We kind of divide our array that way. And what's keeping track of that is this heapSize variable.

[00:06:35]
That's when you're doing a createMax Heap. You're just passing array.length as the heapSize. Whereas this changes here for this heapify code. Hopefully makes a little bit of sense. All right, let's get into the heapify. This is just a lot of conditional logic here. So let's grab the left and the right child.

[00:06:57]
That's the first thing we'll do, left =2* index + 1, right? And same thing here, right, is that + 2, okay? So for whatever item in our array here the index we now have the left child and the right child. And we're going to say if heapSize>left and array(largest) let's see.

[00:07:41]
I forgot to do this variable as well. Let largestvalueindex=index. And so what I'm just gonna keep track of in this particular variable is, where is the largest values index, and then I'll just use if statements to check. I'm sure there's a more elegant way you could probably do this.

[00:08:02]
I was just trying to be clear. So largestvalueindex> array( left), then largestvalueindex is assigned left. And then we'll ask the same question for the right side. In fact, you could probably even just copy and paste it and modify it a little bit. Change this to right. In fact, everything just changes to the right yep, so right, right, right.

[00:08:40]
So I had to change right three different times there. Okay, so after asking these two questions. We all know is the parent, the left child or the right child, the largest item of those particular three. And then all I have to do here is I have to say, if largestvalueindex is not equal to index.

[00:09:08]
So basically do I need to do something if, so first thing, swapPlace of index, largestvalueindex and array, okay. So this will actually do like the swapping that we were talking about and then. We just need to make sure that we call heapify on the child array, largestvalueindex and heapSize.

[00:09:48]
That's it should be. Let's go ahead and run this make sure that I'm not telling you sweet little lies, And none to do that. But that, it's not running. Why is this not running, please run. I didn't call it the test I skip down there. Now let's try it.

[00:10:20]
Run, run, run, run, one failed. Array is undefined, and where's that? 14. CreateMaxHeap, I didn't return the array, return array. So line 23 there, I had to put a return array. Let's try that again. There you go, that worked. So yeah, make sure down here you are returning the array though honestly.

[00:11:14]
You could have just said create Max because it modifies the array itself anyway. Right, make sure that I'm not telling you more lies But yeah, that should work, it does. Either way, we'll leave it like that because I have it in my notes. I like doing things like this where I say it's assigned to this.

[00:11:38]
So people are aware, hey array here it's getting overwritten, despite the fact that semantically it ends up being the same thing. Okay, any questions about heapsort?
>> Yeah, confused by recursion. What's your base case, how does it exit, how does it stop?
>> Yeah, so the question is, what's the base case in the recursion?

[00:12:01]
Valid question because typically we want to put it up here, right? So it's pretty obvious, in this particular case, the base case is when you start going out like either a swap doesn't happen or you go out of bounds. So I guess that either case, it's when a swap doesn't happen, right?

[00:12:17]
So this only happens when largest value index changes, and eventually you're going to go outside of your array, right? So, eventually you're going to start asking the question is like, looking at this one, Like 7, right, or index 8 here. This doesn't have any children, therefore swap cannot happen, right?

[00:12:41]
And therefore that's the base cases when there's no swap to happen. Does that make sense?
>> Yeah, it makes sense.
>> Cool, good question, thank you, other questions? So how does the number heapSize change over time? Is that a fair assessment of the question?
>> Yes, that's correct, I just forgot the link.

[00:13:00]
>> That's good, yeah, it's a weird word. So the, how does the heapSize change over time? So let's talk about because heapify is going to change and we kind of use it in two different places. It does the same thing. But we use it in two different ways, kind of.

[00:13:17]
So the first time we use it is here instead of createMaxHeap. And this is where we were starting in the middle. Again, if we go up to my example up here, right, we start here, when we're doing createMaxHeap. And the reason why we don't start there is because these don't have children, right?

[00:13:37]
So we would never have to swap them with anything because they have no children to swap with. So we start here because this is the first one to guarantee to have a child, right? So here, the entire array is the heap. We have nothing on the sorted part of the array yet, this entire thing is considered the heap.

[00:13:54]
Therefore, that's why here, the heapSize is the array.length. Now when we get down to this part here, which is we're actually doing the sorting. Let's scroll down to that. Now the heap size is not actually all ten elements of the arrays, right? Now the heap size is just index 8 and below, right?

[00:14:20]
So the first 9 elements in the array. So that's why heapSize on this very, very first iteration. There's gonna be a 9, yeah 9. And that's gonna decrease over time, right? Because this sorted part of the race you have 10 here, then 9, then 8, then 7. So it's just gonna work backwards, until eventually, the entire array ends up being sorted.