Implementing Heap

[00:00:00]
>> We just got done going through everything that has to do with a heap. And I do want to implement a heap. I think we hopefully we will still have time for everything else today but I'm very, very excited to implement heap. Like I said, I do think it is literally the funnest data structure to implement.

[00:00:16]
So again, go to your Kata project, go to heap. We are gonna implement a MinHeap, fantastic. I'm super excited. So, in this case, since we're implementing a MinHeap, since we have an array list that's actually underneath the hood for JavaScript, we're just simply gonna use a JavaScript array for this.

[00:00:33]
And everything should work out because it already is the data structure we want. So, I'm gonna have a private data, which is going to be a min heap, which is just literally gonna be a number array, right? We're storing numbers, we need the minimum, let's go. You could make this a more complex item by having something like some sort of generic in which extends something else, right?

[00:00:52]
We could do that. I never remember the TypeScript definitions for all those things, but there you go. We pretty much have what we need right here, which is the length and the data. Remember the length is used for insertion and deletion and so it's very important to make sure you maintain that link.

[00:01:07]
So, this.data equals that and of course this.length = 0. Now, I'm pretty pumped, we have two methods we need to do, which is insert and delete. Delete obviously pops, off we could read, I've seen delete often called poll or pop. So, however you want to call this thing, go for it, but for the sake of this program, it expects delete.

[00:01:31]
All right, so, we do need two private functions, or actually five private functions before we keep on going. And remember, this comes from this part, which is we want heapifyDown, heapifyUp, and we want to be able to get all these indices right here, right? This whole equation we should probably make into functions, so we don't have all these two times indices this, that, and the other, cuz if we have a problem, we're gonna be hunting all over our code.

[00:01:56]
So, I'll start first with parent, right? This will return a number which is the index and it takes in an index. Awesome, so let's just return that. Remember, what is the equation? It's Math.floor, go back, capitalize Math, because that's what you do. And it's (idx- 1) / 2.

[00:02:14]
Let's just double check. Remember right here, parent index operation. There we go. So, we now have our ability to grab our parent from any index. This will obviously help and then heapifyUp. And if we were to write update, it would also be used in update. All right, awesome.

[00:02:32]
So, let's do another one. Let's get a leftChild (idx: number): should return back out a number, correct? So, one thing we're gonna do is we're not gonna consider our length when doing this. We will use our length as a way to know if the child exists, but we will not use it during the actual grabbing of the index.

[00:02:53]
So, we can just simply return idx, what is it, it's idx * 2 + 1. Yeah, yeah, right there. Then simply call the next one a rightChild and turn that to a 2, right? They're almost the exact same thing. So, there we go. We're already mostly through our heap implementation, at least some of the harder parts, to make sure you have correct.

[00:03:16]
I'm just kidding, those are actually the easiest parts. But that doesn't mean we can't write the hard parts. So, heapifyUp, this is easier than heapifyDown cuz when you think about it, heapifyDown, you first have to find the minimum child, then you do the comparison, then you have to swap.

[00:03:34]
Whereas heapifyUp, we only have one value we need to look at, which is the parent and we keep doing it until A, we're off the board or B, we're larger than, right? Cuz it's the min heap, min heap means if we're larger, we don't bubble up. Yeah, pretty straightforward?

[00:03:50]
I think it is. All right, so, let's heapifyUp, starting at an index. Now, this can be either recursive or iterative, whichever way you want to go. I don't know which way I'm gonna write it, let's just find out which way feels easier. In some sense using it recursively, again, always really easy because one, you can just do something as simple as this, if (idx === 0) we're done.

[00:04:13]
You cannot heapify beyond the 0th index, right? heapifyUp stops there. So, it's just as easier though it's not as performant, but we'll do it anyways cuz I just like the look of it. So, that means we're gonna do a quick check. We need to get our parent, get its value, check if we're larger than it.

[00:04:32]
All right, so let's do that. const p = this .parent, and then, of course, the current index we're in. The value, of course, is this.data[p], right? We have the value of our parent now, right? So now, all we have to do is check if our value whoopsies, here we'll call this parenV.

[00:04:54]
Sorry, I mean, I always battle between doing the algorithmic way, which is these really crappy single letter variables, or writing it all engineering-wise. Let's see. FV, there we go, parentV. So, if (parentV < v) than we are, what do we need to do? Nothing, right? Correct, cuz we are a min heap, but if (parentV > v) what do we do?

[00:05:24]
We need to go up, we're a min heap, we're trying to go up as far as we can until we are now larger than our parent. So, this of course means we're gonna heapifyUp with our new index, but what is our new index? Our parent, right? We'll heapifyUp based on our parent's position, but we need to do one more thing.

[00:05:49]
We need to take ourself and swap it with our parent before we do that, right? We need to swap, heapifyUp again, swap, heapifyUp again, and we just keep on doing that. So, const tmp, we already have a tmp, which is our parent. So, that means this.data.[idx] = parentV.

[00:06:09]
And of course, this.data[p], our parent index = v. We've just swapped them, and we're gonna try again starting at p. Does that make sense? Yeah, I think so at least, I think so. There we go. Look at how simple it is when you do it recursively. We can do this iteratively, it just means we simply need to hold on to our current index and do probably the Lord's loop a do while loop.

[00:06:34]
It's just like PHP, it's the greatest thing ever. All right, so, I'm gonna keep this one recursive cuz it just feels fun to do it recursively. We can do the other one iteratively if we want to. So, now we need to do the last function, heapifyDown. Now remember, this is when we do a deletion, we need to remove the head element, take the last element in our array, put it into the first position and then do that beautiful, beautiful operation of heapifying down.

[00:07:01]
So, one thing we could do right here, is we could actually write this swap as a function so, we just don't mess things up. Cuz we're gonna have to obviously do some swapping in both insertion and deletion, or at least an insertion, but we're not gonna worry about it.

[00:07:14]
So, heapifyDown starting at this index, let's go. Void, awesome. So remember, heapifyDown has a couple conditions. First condition is the base case. If our (idx >= length), right, if we're already at this point, we shouldn't be heapifying anymore, right? We would heapify clean off our array, we'd break our case, so we can return right here.

[00:07:43]
Second, what's the other one? There is another one, but let's first find out what it is. So, let's go like this, left index, whoopsies, lIdx, which is gonna be this.left Child, and then rIdx. Let's get the two indices, and now that we have the two indices, we can do a simple check to find out if we have any more children.

[00:08:06]
How do you know we have more children? Well, simple trick. If we always fill in from left to right, if our left index is greater than or equal to our length, we have now officially left where any of our heap nodes are at, right? That makes sense, so we can do the exact same check again ,this.length and then we can return.

[00:08:31]
We can also simplify this logic if you don't mind doing those operations before checking and then we can just simply do this right here. All right, and there you go. Feels a little simpler, right, just depending on how fast you wanna make the code, right? You didn't have to do this multiplication, two times multiplications much much more expensive than addition plus you're also doing a floor blah blah blah blah blah.

[00:08:56]
But often if you're writing JavaScript, multiplication is probably not your bottleneck, just throwing that out there. It's probably the factor using JavaScript, that is the reason why it's slow. All right, so, we need to heapifyDown, we need to be able to get both these values, find the minimum one, and then compare and tell do we need to swap?

[00:09:16]
So, let's first find the minimum, child of course. So, we can go like this, minValue = let's see, we can do like a quick Math., well, we first probably should grab the values, lV = this.data[lIdx], rV = this.data[rIdx]. There we go. So, we have our two values of our children.

[00:09:39]
We can even grab rV right now just to make this easy, which is going to be idx, there we go. So, we have rV, their two values. Now time to do that fun comparison, and so, which one do we want to do? We can just do this in the simplest version, if (lV < rV), why not?

[00:09:57]
I'm sure we could program this much more elegant, I'm sure there's a math.min solution out there, but it also sometimes gets a little too clever by half. All right, there we go. So, if this is the case, we simply will do this. If (lV > rV), that means our right value is the smallest and our value is less than r, let's say we were doing a min heap and we're heapifIying down, and if our value is greater than right value.

[00:10:25]
So, in other words, our right value is going to be the smallest and we are greater than the smallest. Therefore, we need to swap and heapifyDown. Does that make sense? I think so. All right, this.heapifyDown, of course, and we're gonna want to use rIdx, but again, we need to do the old swapping of the values.

[00:10:47]
So, let's swap the values, this.data.[idx], = rV, this.data[rIdx]. My goodness. Needs to equal, what is it called? Rvalue, there you go. I don't know why that took me so long, there we go. We just did the little swapping, so we could do the exact same thing again. Put it right here, go here, do a little else and then just swap everything around, right?

[00:11:11]
If (rV > lV && v > lV) then we need to swap out our left value, so we can just simply do a little rl, rl, rl and that's it. That's all it is to heapifyDown. It's really not all that hard. It's actually a rather simple implementation. Of course for those that are wondering, why would you ever want to do it this way with all these if statements, why not come up with a more elegant solution?

[00:11:40]
My general rule of thumb is I don't refactor unless if I see a rule of three, Martin Fowler, great book, highly recommend. There we go. So, this is fantastic. I'm very, very happy about this. So, we believe we have heapifyDown correct, we believe we have heapifyUp correct. So, now it's really just time to implement our interface.

[00:11:59]
So remember, let's go back to this and talk about insertion. Insertion is where you first put it at the end of your array, right here. And then at the end of the array, we need to heapifyUp at that position. And so, what of course, is the end of our array?

[00:12:16]
Well, it's our length. So, this.data[this.length] = value. this.heapifyUp(this.length). Whoopsies, there you go, it's literally that simple. But we have to do one last thing. We can do a little ++ right there if you wanna be cheeky about it. Or if you don't wanna be cheeky and get called out in a code review, just do it right afterwards, there we go.

[00:12:39]
So now, we have this beautiful thing where we first use the length to set our child in. We then heapify it up or bubble it up to the top, then we increment our length by 1, that was actually rather simple, right? Now that you have the pieces together, this is just absurdly simple.

[00:12:52]
I'm also a little shocked this is going as well as it is. All right, so, deletion is where it gets a little bit harder, right? We need to know some things. One thing is that what happened if we have no elements in here, what should we return? === 0, well, since our interface is just a number, why not?

[00:13:11]
We could return -1 as a sentinel value, but then you're arguing well, hey, that kinda sucks cuz of this, this, and this, we could technically make this into an undefined and then return out an undefined, right? Hey, that's terrible, you shouldn't be able to do this blah blah blah blah blah, we could come up with our own ways to be able to do this.

[00:13:28]
That's very JavaScript even have the fact that you can try to remove something in which does not exist. That doesn't usually happen in other languages, usually you get kind of like a hey, don't do that. I guess Rust, you have options. So, we'll just do that for our case, why not, we'll call this good enough, we don't really have this notion of an option, so there we go.

[00:13:47]
All right, so now we need to do the exact same thing except in reverse ordering. Which means we first take our head, we get its value out, then we have to take the last element in the array and put it into our head's position and then bubble it down or heapifyDown.

[00:14:07]
Does that make sense? So, there is kind of a second condition, if you really wanna think about it. We could also go if this.length = 1, right? This is just a real problem, right? That means we could just go this.data = [], right? Or const out = this.data[0]; return out; right?

[00:14:27]
Very, very simple, we kind of just addressed that one situation that may be a little bit more tricky than the other one. And then we can just finally do the heapfying right here, which means we're gonna have our out, which we can actually move this thing right here, beautiful.

[00:14:39]
We have our out. And now all we need to do is heapifyDown. And then we have to figure out, do we heapifyDown and then reduce the length, or do we reduce the length and then heapifyDown?
>> Reduce then.
>> Reduce then, exactly. So, the reason why we want to do that is we don't want to get ourselves in trouble, because if you remember, heapifyDown does consider length as a part of this operation.

[00:15:05]
Which means we could find ourselves in a bad situation and even more so, notice that as we delete out a value, we may not be zeroing out the value, right? In other words, you may have numbers or pollution within the part of the array you're not using any more.

[00:15:20]
So, could be very dangerous if you don't set your length properly. All right, there we go. Set the length properly. And now we just simply heapifyDown starting at the 0th position, right? We've just, I forgot the most important part, right? this.data[0] = this.data[this.length]. Yeah, that thing. Isn't that great?

[00:15:42]
There we go. Reduce our length, we're now pointing to the last element properly. Move that to the 0th position, heapifyDown. Make sense cuz length is always exclusive. Therefore, by removing it one, we made it inclusive for a moment. Put it up there, now we're good. Okay, fun little trick.

[00:15:59]
We didn't have to do it that way, it could have been a little bit more obvious if I would have done that and then did this, but it just feels good to be tricky. There we go, super tricky, awesome. And I think this is everything we need to do other than the whole fact that I forgot to return out, there we go, so, we should be able to return out.

[00:16:15]
So now the real question is, did we get this correct? I think we got this correct. The good news is we also have a test to run, jest Heap. If we run the minify heap, hopefully we've done everything correct and look at that. We didn't do it correct.

[00:16:34]
This is one of the saddest days of my life right now. I'm gonna call my mother. I will cry, many things. We did not get this correct, because we added in one condition in which we did not do correctly. Can we please get an RIP in chat? If we would have simply done this, we would have been fine.

[00:16:57]
Isn't that just the saddest? Isn't it just the saddest? We simply forgot to decrement or length when we only had a length of 1. There we go. Classic blunder. There we go. That is a heap. See, they are fun to implement. They have a really kind of a cool concept to them and we're just playing around with a raise, which I think makes it a ton more fun.

[00:17:20]
So, there we go. Hopefully you enjoyed this. Is there any last minute questions that would like to be asked about a heap? There's one thing we haven't covered yet with a heap. No one asked about the running time. The running time, what is the running time of these two operations?

[00:17:37]
What is the running time of an insert? What is the running time of a delete? Remember, we're gonna normally consider worst case scenario in this. So, what is the worst case scenario? Well, it's gonna be you start here at the bottom and you try to bubble your way all the way up to the top.

[00:17:52]
Or you're gonna start from the top and you may have to bubble your way all the way down to the bottom. What is the height of the tree? It's always log n, because this is a complete tree at all points or a full tree at all points, it always fills in from left to right, there are no gaps ever.

[00:18:09]
So, log n for both operations. Now, there are different trees that actually even give better solutions, Fibonacci heaps. Which, just mind blowingly complicated, there's no way we could possibly cover that, it would probably take four hours just to get really all through it, but it's fantastic, it's awesome.

[00:18:26]
I still don't quite actually get exactly how they work. I don't know if I could program it first try, but it's fantastic. So there you go, hopefully you enjoyed this. Hopefully you understand now, of course it's log n cuz every single layer multiplies by 2, half the tree is always in the bottom layer, therefore blah blah blah blah blah.

[00:18:45]
We already kind of gone over that a few times. All right, I already talked about this, careful about garbage. Your array may contain some items if you did not properly clean them up. So, be careful. We're using a number array, so we don't actually have to be careful.

[00:18:59]
But if you're using an array that's generic over t, you may want to put in something like null or undefined. Make sense? All right.