Everybody has gone this is Caleb with Dev slopes and in this video we're going to be talking about the
heat data structure and we're also going to learn how to build one in swift which is pretty neat.
So first I want to just kind of review what the heap is and how it works.
Basically heaps can operate in two ways.
Ms.
Heap or max heap heap basically prioritises the smallest values at the very top and a max heap does
exactly the opposite it prioritises the largest values at the very top.
Now each heap starts with a parent node and then it can have two children nodes just like so.
So this top one has two children.
This one here is a parent.
It has two children.
So a node can act as both a parent and a child except for the very tippy top.
So another thing to know is that the child nodes are always bigger than their parent nodes so here too
is the parent and the children are 3 and 8.
Both are bigger here.
Three is a parent node and four and seven are both its children nodes which are both bigger.
So that's how that works going down.
Another thing to note is that the index of heape items start at zero just like an array and then go
top to bottom and left to right.
So we start with 0 then one two three four five six seven eight nine 10 et cetera et cetera.
And what we need to be able to do in our heap is to be able to access the index of a parent node for
a child node.
We also need to be able to access the indices of both children from a parent node and we're going to
write some code to do that but we also need to think if I add in a new item K like down here at the
bottom maybe index 21 or something.
It needs to be able to tell whether or not the parent node is larger than that value and if it is then
we're going to switch it until it fits where it's supposed to be in the heap.
Now you might be wondering why would a heap ever be useful in real life.
Well think about this imagine that we are using a max heap where the largest values are prioritized
and moved up to the top and the lower values are more down towards the bottom.
Now of course you can tell it's not perfectly organized where it's going you know in numerical order
like 2 3 4 7 8.
It doesn't work that way.
But generally speaking the largest values are at the top and they're prioritized that way.
So obviously a heap gives you the minimum value at the top of max heap gives you the maximum value at
the top.
So imagine that you're working in a hospital and their intake system for new patients maybe at the emergency
room is a max heap because they want to prioritize the oldest people who come in first they should receive
care first.
Maybe that's how it works.
So let's say someone comes in there add it into the heap and maybe their age is you know 75 and we're
we've got to think about this fliped because this is a min.
But basically their value would be bumped up to the top and they would be put in priority number one
because they are the oldest.
As soon as maybe they have received care they can be removed from the heap and then the rest of it would
bubble all the way up and so that the next oldest person would be at the top.
That's how they work and that's how they could be useful.
The same could go for maybe a pediatric clinic where the youngest children would be prioritized first.
OK.
So let's go ahead and let's pull up an X code and let's build a heap.
So get started with a new playground and we're going to go ahead and just create a blank playground
and let's just call this heap of find the cap'n just save it wherever you want.
I put mine on my desktop.
I want to make the window full screen here and get rid of all of that and just import foundation because
we don't need any of the fancy kit stuff in the playground.
For now we just need foundation because we're using Swift.
So let's go ahead and let's create a struct K called a mean heap and that's what we're going to do.
We're going to create a heap that is a mini heap we could create just a heap struct and then write all
the functions for min and max and maybe use some type of enumeration to determine whether it's min or
max.
But for now let's just go ahead and focus on a min heap because a max heap is exactly the same just
opposite.
So we're going to write some functions in here that are going to be private that only the struct can
access inside and they are important there are three groups of functions.
The first group of functions is going to be for getting the index of a particular node get left child
node get right child node and get parent node or I should say index rather than node.
And so what we're going to need to do is to first write the function that's going to get us the index
of the left child because let's imagine that I am a parent here and I want to know what the index is
of maybe child on the right so I can do a formula and a function pass in my index end depending on my
index I could basically tell you where it is and what index it's at.
So we're going to start by writing a function to get the left child index and it's going to be a private
function called Get Left child index.
We're going to pass in the parent index here.
And of course that's of type and because an array uses it as its way to manage indices.
And because we're getting an index back we need to return an integer.
So in order to actually get the index of the left child we're going to return to k times the parent
index plus one can let me show you how that works.
So this is our first item and it's at index 0.
We're going to use an array actually to store our heap because the index format is the same.
So index 0 is here so we're going to do two times zero which gets us 0 plus 1 gets us the left child
node.
Very very cool.
That's at index 1.
Now getting the right child is going to be basically the same.
We're going to add two instead of one.
So private phunk get right.
Child index like so we're going to pass in the parent index of type int and we're going to return an
integer because of course we're getting the index.
So return to Time's parent index plus 2.
And that works the same way.
This is index 0 2 times 0 0 plus 2 gets us to.
So index 2 is where the right child is so we go 0 1 2.
There's our right child and it works for any of these.
This is index 1 2 0 1 2 3 4.
So if we wanted to know the right child index we would take four times two which is 8 and then plus
2 which is 10.
So 0 1 2 3 4 5 6 7 8 9 10 gets us the index of the right child.
It's pretty cool.
So let's go ahead and let's write the function in order to get the parent index.
That's also going to be a private function.
Get parents index.
And we need to pass in the index of a child.
So child index of type int.
And we're going to go ahead and return an integer and the function for this is we're going to return
a child index minus one.
All right.
And then that whole thing is going to be divided by two.
Let me show you how that works.
So this is well let's see we're getting the parent index of this so we should get the index too.
So what we're going to do is we're going to take the index of this node 0 1 2 3 4 5.
And what we're going to do is we're going to minus one.
So five minus one is four and then we divide that by two which is two.
So 0 1 2 The index is 2 for the parent node.
So now we have the functions we need in order to actually interface with our heap and that's cool and
all but let's go ahead and let's compile these together.
These are functions for getting the index.
And that's great.
So let's go ahead and let's move on.
Oh that's weird.
It looks like that curly bracket turned dark on me there for a second.
Now we need to go ahead and basically write some boolean check functions.
And these are going to check whether or not an item has a left index or right index because in some
cases it might not.
Right.
This parent has a left child but does not have a right child.
And so that would tell us that's where that item needs to go.
Pretty cool.
So we're going to write some functions to determine those different things.
Private funk has left child care and we're going to just pass in an index.
OK.
We're going to return a boolean.
All righty.
And in order to do this we're going to go ahead and say return get left child get left child index already
and we're going to pass in whatever index we have.
So let's say you know it's a parent at index four and we're going to get the left child of that parent
index.
But what we're going to say is if that index is less than the total amount of items in our heap.
So let's think about this if our help here is well let's see this.
If this was the 20th item so 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 what that means is that there
are really 18 items.
So if the index here is 17 and if that is less then the total number of items right the index is 17
the total number is 18 right.
So if that is left.
Sorry if that is less then that means that there is a left child index.
OK.
So what we're going to do is we need to actually create the array that is going to hold all of our heape
items.
So go ahead and create an array called items WIPs items and it's going to an array of type int if only
I could type and we're going to go ahead and just initialize it as an empty array here and we're going
to say if it is less then items don't count.
Ok if that's true it'll return true if it's false.
For instance index 0 1 2 3 4 5 6 7 8 9.
OK.
So we pass in the left child index of 9 K and we get what the child index should be which in this case
would be 19 it 19 is not less than 18 so therefore it knows it does not have a love child.
That's how it works.
So we're going to do it again but do it for the right child which is actually going to be the exact
same function.
So for time's sake I'm just going to copy and paste it and just change the wording so it has right child.
We're going to use the function.
Get right.
Child index.
And if it's less than items that count.
We know that we are not doing the right thing.
So now we need to write the function to check if a node has a parent.
OK.
So private phunk has parent and we're going to pass in the child in the well let's just say in next
gen has a parent.
We're going to check and return a boolean.
OK.
Mix some more space.
You can see what I'm doing here.
And so basically what we're going to do is we're going to return get parent index all ready.
We're going to pass in the index and if that index is greater than or equal to zero.
Right.
We know that there is a parent because.
Yes.
So if let's say we pass in you know index one here.
If one is greater than or equal to zero it has a parent here.
If it's greater than or equal to zero it has a parent.
So basically everything will have a parent node because this index 0 is equal to zero.
And so this node is a parent obviously and it is its own parent which is kind of weird to think about.
But anyway that's how it's going to work.
Code wise.
So now what we need to do is we need to be able to return a certain item from the heap.
Right.
So we have our array of items we need to be able to return an item.
So this is our third section of functions and it's going to just be functions that return an item from
the heap.
So we're going to write three more private functions here private funk and this one is going to be to
return the left child K at a particular index and what it's going to do is it's going to return an int.
So in order to get it we're going to return something and it's going to come from the items array and
all we need to do is to get the left child index wups get left child index.
And for you know a particular index.
So that will return the item at the index that we set.
Right.
So let's say that we're talking about a parent node and we want to get the left child we can actually
just call the index from the parent and it will return the love child for that parent.
So we're going to do the same thing here for right child and I'm going to just copy and paste it for
time because it's the same exact thing right child.
But we're going to use our right child function.
Next we need to be able to get the parents so private phunk parent.
All right.
And we're going to you pass in an index here of type int and we're going to return an int.
Now we're going to return items.
OK I'm going to pass in get parent index for index so if we pass in the index of maybe a left child
this will tell us what its parent is which is pretty cool.
So now this is where we're actually going to write out the operations for our heat.
And like I said when we're dealing with a heap if we added a new value say three here we need to be
able to check to see if this value and its parent are in a good relationship and right now they're not
because 3 is smaller than 9 so it should be in this place.
So what we're going to do is we're going to swap these two and then we're going to check it again.
So we're going to swap the index of three and nine and then we're going to check OK three is still smaller
than four so we need to swap three and four.
And then obviously three and three are equal so they can be in the same place here and that's fine.
But we're going to move on.
So we're going to go ahead and write the swap function which is going to swap two items.
And so let's go ahead and just call this heape operations and this function is going to be private as
well because it just needs to happen on an internal level private function.
So WAP.
OK.
Index one of type int and index to of type int.
And this is not going to return anything we're just passing in values and mutating them so we're going
to basically save one as a placeholder set.
The other one and then set the first one back to whatever we stored in the placeholder so let placeholder
equals items at index 1.
All right so we're going to save that in that little constant there.
Then we're going to say items index 2 is equal to items at index 1 like that.
And then oh wait no I'm doing this backwards.
Index 1 is supposed to be set to the item at index 2.
All righty then we're going to go ahead and set items.
Index two to be equal to the placeholder text we are.
We changed the value of index 1.
We just stored it in memory there which is pretty cool.
And then all that's doing is just swapping the place the index of two variables or two values I mean
in our function.
Now we are getting yelled at because it's saying that this function inside of a struct needs to be marked
as mutating because it's actually mutating the way that items is lined up.
So let's go ahead and add the mutating keyword there and our little error message will go away because
it can then have the permission to mutate the items right.
So a heap has three functions very similar to a stack we have peak Paul P O L L and add so add is like
push pull is like pop and peak is just like peak.
So we're going to write those three functions now.
These ones peak pull and add are all public.
They're ones that we actually want to interface with because Peake allows us to look at the very top
item of our nodes so we could check you know what patient is in that spot.
Were talking about our hospital metaphor pool is going to remove the top item and return it.
Okay.
And then add is going to push a new item in.
So let's go ahead and write this one public phunk peak already and it's going to return an integer to
us.
And so if items that count is not equal to zero.
All righty.
We're going to go ahead and return item at index 0 because that's the top item in our right.
But if that is not the case if if items that count is equal to zero we're going to call fatal error.
Ok cause that would be a problem.
There's nothing in our right.
So that's how peak works it's going to return the top item.
Now we're going to go ahead and do another public function here called Paul and Paul is actually going
to return an integer as well like so.
But we are going to be modifying the array because if we remove an item and then return it.
So we need to set this to mutating.
Now what we're going to do is we're going to check again if items that count is not equal to zero.
We're going to do stuff like modifying the function and removing it then we're going to go ahead and
say else if there is zero items we're going to call fatal error.
So here we go.
What we need to do is we basically need to store the item at the first index so let item equal items
at index 0.
All right.
We're going to just save that in its place then we're going to do is we're going to go ahead and set
items at index 0 to be equal to the very last item which is the new one that we have added or most recently.
All right.
So we're going to call items items dot dot count minus 1.
So we're going to go ahead and move the last item in our heap K all the way up to the front.
Okay.
And then what we're going to do is we're going to go ahead and call a function called heap of FY down.
We haven't written that yet but then basically what we're going to do is lie down is going to basically
check the indexes and say okay 18 that is bigger than both of these and needs to go down.
Okay 18 still bigger than both of these needs to go down 18 still bigger than both of these it needs
to go down 18.
So and it's basically going to help it go all the way down to where it needs to be.
This is what we're doing is we're removing the first item and then we're here refining everything so
that everything knows where it should be.
Now what we're going to write the function down in just a second.
But then at the very end after we reorganize everything we're going to return the item that we initially
saved and removed.
Okay.
So that's Paul that's going to remove the first item and then return it.
And now we need to go ahead and create the add function.
So it's going to be a mutating function and it's going to be public and we're going to go ahead and
just say add and it's going to be an item of type int because that's the type that our function is.
And so we're going to go ahead and do that.
We're going to say items append add the new item and then we're going to need to heap ify up.
OK because if we add a new item down here at the bottom like it let's say it's three that should be
switched with this so we're going to keep it up goes there.
We're going to fly up again and it'll stay there.
OK.
So that's where people fye up comes in handy.
So this video is getting a bit longer than I had anticipated.
So we're going to go ahead and cut this one short and head over to the next video where we're going
to actually write it down and he picks up functions in order to rearrange our heap and then we're going
to actually create an instance of it and play around with it so you can see it visualized.
Let's head over to the next video and let's keep learning about the heap.