OK.
Welcome to another lecture about heaps in this lecture, we are going to be using the hip affi algorithm
that we have learned when we discuss deleting leading to actually build a heap and we're going to build
a heap in place.
So what we're talking about is you already having an array with values, but they do not represent a
heap and we want to turn it into a heap by usage of this heap of AI algorithm.
So let's say we already have an array and you won't be looking at this already and be like, well,
you said that it wouldn't be in a heap, but it is in a heap.
This isn't a previous example we've used, but it is a main heap.
And what I'm proposing we do is turn it into a max heap.
So that means that it would not be in the form that we want this in the mini heap, not a max heap.
So let's go ahead and use simplified to turn this into a to.
So what we do when we're trying to transform this into a mass heap using typify is to repeatedly use
heap of fire starting at the last parent node in the heap and moving backwards.
So that means moving from the bottom right to the left and up.
So none of the complete bottom ranks.
I said that we start at the last parent node, so we're not considering leaf nodes.
That's like a big plus of the algorithm, and it makes it faster as far as time complexity.
So let's start at 21 over here.
You can find the last parent node in the heap.
Add in over two minus one, where in is the number of nodes in the heap or number of values.
Considering that as an array, so this will iterate through the heap backwards starting at this point
and repeatedly do that heap of fire.
There's no heap of fire for us to really do at this point because you notice, of course, there's only
one node and it's equal to the parent node.
And we already discussed that being equal is OK and requires no swapping.
So we will move to the left on the same level, right.
So we moved to the left and now we look at five, if you think back to your five, what we want to do
is pick the bigger of the children and swap the parent node with the bigger of the children.
So obviously that is twenty eight.
So we will perform a swap and we swap five and twenty eight.
You can see that swaps in the array as well.
So we're actually done with this level now.
This is a very small example, but it'll be useful to help us understand without going too deep with
some massive heat.
So since we're on this level, we go up to the next level.
This is already the root level, so we would start at the rightmost node.
But this is the right most node because there's only one, right?
So you can see it's reflected in the array as well as the zeroth element at the first position.
So let's go ahead and pick the bigger of the children.
So we look like it looks like we have 28 and 21.
So obviously 28 is bigger.
So we will perform a swap and this is where we start the heap fi process of 15 down, right?
So we've done that swap and we're not done yet because we still have to consider the children of this
node, so have to continue heap refining until we cannot go anymore.
So we pick the bigger of the children now, and 25 is definitely bigger, so we go ahead and swap three
with 25.
You can see that reflected in updated in the array as well.
And now we notice that we actually have a max he already.
So not too many steps, it was a small example, but it's not too many steps in general because it's
a very efficient algorithm to transform an array into a heap.
So you notice let's check the property right to make sure everything is OK.
So structurally from the beginning, it was totally fine.
Of course, any ray, you know is going to be fine, but we noticed that if we were to build out a heap,
we would want it to apply to apply the structural property.
But the numerical property is OK as well, too.
So 28 inch children are 25 and 21.
Those are less than we could.
25 inch children are five and three.
Those are less.
And of course, 21 and 21.
Being equal is fine as well, like we talked about before.
So in terms of efficiency and time complexity, we haven't really covered formal analysis of algorithms
yet in this course.
So you're going to have to just trust me that this bill heap with heap of fire runs in linear time so
of in.
And you can even claim type bound state of in if you're familiar with that, and you can check that
out at this link here.
But it depends on how you implement the algorithm, of course.
So after you're comfortable with the algorithm analysis portion of this course or you already understand
how to analyze algorithms formally, you may wish to read about the informal analysis of this algorithm
at the following links.
So this link right here I will put in the resources section as well.
It talks about heap sort, but it also has this build heap with heap of fire and in the initial section
of the paper, and they do a good job explaining why it runs in linear time.
And they compare it to the other build heap that we discussed, which I believe is in log in time.
So that would be worse than just in time, right?
Linear time.
So I am not going to go over the code for these heap algorithms.
They are just implemented with an array, but I encourage you to attempt to implement them, right?
You can just use an array and use the properties we discussed to show where the parents and children
are.
And it should be pretty simple for you to come up with an abstract data type.
Right?
You could make an abstract data type, have a data member as an array, and then you could just go over
what I showed you in the theoretical lectures to implement these algorithms to be able to build a heap.
So with that, we will conclude our discussion about heaps we might later on mention them in the algorithm
analysis section or if you feel comfortable now or after that section, it might be good to check out
this link to see why heaps are so great and efficient and why this specific build heap algorithm is
very efficient.
OK, so with that, I will see you in the next election.