Everybody else is going this is Caleb with Dev's slopes we're going to continue learning about the heap
in this video we're going to write our down keep up functions and we're also going to create an instance
of our men heaps struct and actually play with it interact with it and printed out so we can see how
everything is getting organized.
So let's go ahead and let's continue this by writing our heap of five function.
And these are both going to be mutating private functions so mutating private phunk OK because the heap
of five function only really needs to be known by these functions here and inside of our struct.
We're not going to actually call ify up or down when we're interacting with our heape that's not how
it's supposed to work.
So we're going to go ahead and create this function now heap of fi let's do up first.
All righty.
As you can see it kind of auto completes there which is cool but what we're going to do is we're going
to go ahead and save the index of the last item in our items right.
So var index equals items dot count minus 1.
And what that's going to do.
And what that's going to do is it's going to go ahead and save whatever item is at the very end because
remember there's 18 items but the index is 17.
So count it's the total number of items.
And then we subtract 1 to get to the last index.
So we have saved the index of the last item and now we're going to go ahead and use a while loop because
we need to actually go through each item and Fi it either up or down depending on how the heap changes
and rearrange things accordingly.
So he is going to basically move an item up in the heap where it's supposed to go and we already got
a reference here to the last item in our heape which is here at you know item number 17 I believe is
the index.
So basically what we're going to do is we're going to need to check the value of a certain number so
let's say we we did add in three here at the index 18.
So that would mean that 3 now is at index 18 and that is saved here.
18 is the index.
So what we're going to do is we're going to check while that item has a parent.
OK so has parent at index 18 which it does right it would be connected to 9 here.
While it has a parent K and K the value of the parent is greater than the number we're going to swap
them so we're going to use the function here parent K because that is actually returning the numerical
value in this place not the index.
So if the parent at that index is greater than the item K at that index so we need to actually just
stop for a second and think about what we're doing.
So while an item has a parent so it has a parent.
Yup.
And the value of that parent is greater than the value of the item at that index.
So 3 basically we're saying hey if three is greater than nine do nothing.
But that's not the case.
So we need to go ahead and call swap and what we need to do is we need to go ahead and say hey we need
to swap the parent of that item and so we're going to call get parent index for the child index.
And this is actually returning the index value not the numerical value.
So we're going to swap the items at the parent index and at the just the index right because that's
the child.
And so once we have successfully swapped those We're going to set the index to be equal to the parent
index of that item.
So let's talk about that in just a second.
We have successfully swapped the two items.
So now we're going to go ahead and set the index to this item OK which was the parent.
And so now we're going to go ahead and have three in this place at this index.
We're going to do it again.
So while it has a parent check it has a Parent OK.
And the value of that parent is greater than the number so three four K four is greater than three.
So we swap them.
Now this is for and this is three.
So now what we're going to do we're going to do it again.
So while it has a parent Yep.
While the value is greater then no it's the same.
So we're going to just go ahead and stop it.
That is how it's going to work.
That is how we keep ify up.
Now we need to learn how to keep the five down and this one is a bit more complex but we're going to
get through it together.
So mutating private phunk heap of phi down.
OK.
So just like before we're going to store an index.
But since the top always is going to be the same index we're just going to set our index to be equal
to zero.
OK.
And what we need to do is we basically need to check if a node has a child.
OK we need to keep ify them down but the only one that we need to care about is the left child because
if a parent does not have a left child then it definitely does not have a right child.
So while has left the child we're going to pass in the index here.
So let's see.
Index zero.
Does it have a left child.
Yes.
OK while it has a left child we're going to create a variable called smaller child index and we're going
to set it to the left child so get left child index for the parent which is index.
And so what we're going to do now is we're going to check to see hey if it has a right child and the
right child's value is less than the left child's value we're going to go ahead and change the index
so if it has right child for the parent index and the right child at that index k is less then the left
child at a particular index.
If that's the case we're going to go ahead and set smaller child index to be equal to get right child
Index index.
OK.
So basically we're just checking to see if there's a love child great if there's a right child and that
right child the value of it.
So 8 8 is less than the left child.
We're going to set the smaller child index to be the right child because the smaller item basically
is prioritize near the top and then the index changes.
So that basically this is then set as the smaller child and future branches are going to be prioritized
and built upon the smaller branch.
So there's that but we're not done just yet.
So while it's still the while still inside the while loop we're going to say if items at the index of
the parent K is less then items and let's say the smaller child index here k if the item.
So like the actual number at the index of the parent.
So two if two is less then the smaller child index which it is then we're going to go ahead and break
because it's not really important for us to continue because it's already in its place however else
is bigger.
So if this is for some reason 10 we need to swap it until it gets to its rightful place so we're going
to go ahead and call swap and we're going to go ahead and swap the index of the parent with the smaller
child index.
All righty then at the very very end.
We're going to set index to be equal to the smaller child index because basically every single time
we go through this we're going to go ahead and pass in a new value so let's say that we we add in a
new value here 10 right now 10.
In this instance needs to keep ify up.
But then let's say that we keep a five 10 up and it moves some things out of the way and maybe four
gets placed here.
If we basically need to keep that back down to where it needs to go we're going to go ahead and run
this while loop and it's going to go ahead and basically take the index of the smaller child K and it's
going to go ahead and flip it and then reorganize it and then set the index at the very end to the smaller
child so we can keep going down and down and down and down through the process which is really cool.
And at this point we are now ready to play with our heap.
So let's go ahead and let's just create an instance of heap.
So my heape is going to be equal to men heap.
All righty.
And now if we call my heap and we can access the items we can access and peek and poll.
OK.
So let's go ahead let's add some items here let's actually do this.
Similarly to this one let's add in two.
All righty.
Cool.
We two.
Let's just do this a bunch of times.
Let's make this three.
Let's make this eight.
Let's make this one.
Let's do.
No.
4 7 12 13 whatever.
18.
OK.
So we added some items here and now I want to see what they actually look like when we print them out.
So there's a handy dandy function similar to print but basically it dumps an object's contents using
its mirror to standard output.
So we're going to go ahead and dump my heap items.
And what it's going to do is going to print them from top to bottom.
And as you can see our heape is organize.
We have to at the very top its children are three and eight then four and seven then 13 and 18.
So this is actually not organized super well.
The 10 to nine year should be switched anyway.
So now what I want to show you is if I go ahead and type my heape dot peak what that's going to do is
it's going to print out the top item over here.
But if I if I do pull poll is going to go ahead and if you remember poll basically removes the top item
and then sets the last item to be the front and then fi's everything down so that it finds its rightful
place and he profile down is going to take all of the indices into account and compare them to keep
it in its rightful place so if we go ahead and do dump my items after this we'll see a second item and
look at this.
Now our heape is three.
As the parent node.
OK four than 8.
And then for the 4 node the next item is going to be 18 and 7 13 and 8.
So as you can see things are things are organized but they are not exactly in a numerical order like
you might expect.
And so if we continue doing this a few times what we're going to see as we go down is we have to hear
that's the minimum.
Then the next smallest then the next smallest then the next smallest then the next smallest and so of
course we are you know confusing things we're adding things in that are not there.
Oh you know what it looks like it's not actually getting removed which is funny.
So we are running into a problem where our older indexes here are not actually they're not getting removed.
They're kind of getting duplicated and moved around.
So I think we're going to need to do something differently here.
All right.
So I realize what we were doing wrong.
We are going through here.
We're organizing everything the way that it's supposed to be done.
But if you remember in our poll function here we save an instance of the first item then we set the
last item to be the first item then we keep ify everything down and return that item.
Fatal flaw.
We're not removing the last item that we moved into the front.
So we need to call items not remove last.
And now if we look at how this printed it it's going to make a lot more sense.
So here's our initial print which has our full stack two is the parent node 3 and eight are children
nodes four and seven are nodes of three and 13 and 18 are nodes of eight.
So then we remove the one because we call poll and then it reorganizes everything.
Three is a parent node 4 and 8 are its children nodes 17 and 18 are the nodes for 4.
They both are bigger and below and then 13 is the singular node for number 8.
Then we remove 3 and 4 becomes the top parent node with 7 and 8 as children nodes and 18 and 13 as the
nodes for 7.
Then we get seven.
As a parent node 13 and 8 or it's parent or children nodes an 18 is the node of 13.
Then we remove it again.
And of course are our peers getting smaller.
Eight is the parent node and 13 and 18 are its children.
So as you can see it is working we had a little bit of a bug there when we were not shrinking our array
the way we were supposed to.
My bad.
And so this is our heape it works.
It organize itself depending on the minimum value and the maximum value.
We could also set up a max heap by basically you know writing the functions a little bit differently
basically the opposite.
But yes this is our heape.
We can add items we can peek at items we can pull items and when we print it we get them all printed
out in a nice organized way it's doing all the thinking for us.
Very very cool stuff.
This is how you create a heap in Iowa with swift.