All right, so I want to introduce a new data structure that I really like, and this is called a heap.
So we're going to talk about heaps now and we'll have a few lectures on them.
They're really cool, pretty simple data structure that can do some really interesting things.
So let's get into it.
So what is the heat?
Well, it's similar to looking to a binary search tree.
If we're just talking about the things that we've seen so far in the course, so it's the same looking
in theory, but not necessarily implemented in the same way.
And it's also not necessarily used for the same type of operations as a binary search tree.
So let's talk about the defining characteristics of a heat.
So structurally, a heap has to be a perfect binary tree up to at least, but not including the last
level.
What that means is like if you look at this picture right here, let's start up here and kind of encompass
this entire area, not including the last level, right?
So let's go here and all the way over here, I'm trying to draw in a circle around the part that would
be a perfect binary tree.
So let's take a look at that.
Each level actually has double the notes of what the parent level has, so we start at the root and
look at the level below the we noticed that the route has one node, right?
The level below it has two nodes.
The level below that node has four nodes.
The level below that node has eight right one two three four five six seven eight.
So if you think about it, it's kind of like if you start the level zero.
Each level that you go down is basically two to the power of the level, so it's consecutive powers
of two.
So two to the zero is one.
The next level two to the one is to the next level, two to the two is for two to the three is eight.
And if we filled out this whole level, it would be 16, right?
The last level, we do not have to have completely filled out.
But another important property of a heap like structurally is that the heat must be built from left
to right.
So when we build the heap, we actually have to like, let's say we're starting at the root.
We have to fill a left node first before the right node and so on.
So we kind of go down into the right, starting from the left right.
So if we just had one node and we wanted to add another node, we'd have to add this one first and then
we'd have to add that one.
And then we have to have this one and this one and then that one and that one and then kind of fell
into levels like this.
And you notice that's kind of what's happening on the bottom level.
So it's fine that there's like not nodes here like this missing nodes here on this level.
But we could not, for example, let's say we didn't have these two nodes here and we had these nodes
here.
That's not OK.
We would have to fill these two nodes before we could do these two and before we can do these two and
so on and so forth.
So another thing is if the heap is a men heap, every parent node, but must be less than or equal to
each of its children if the parent isn't, if he was a max heaped in the opposite has to be true.
So a heap is really only concerned with whether the parent is less than or greater than the children.
Right?
And in binary search tree, we kind of had like, let's take an example here.
So if we had like five year at the root node, if we got the number three, we would want to put it
on the left right.
If we got the number seven, we would want to put it on the right, right.
So like everything to the right of the root node we're considering would be greater than its value,
right?
Everything in the left would be less then.
So the heap isn't really about that.
The heap is about just having the stuff below these be less than it.
So.
And we're always going to build it from left to right, no matter what.
So what would happen is basically.
You know, we just need to make sure that when you're.
When you have a heap like, for example, this route right here has to be greater than the left child
and greater than the right child if it's a max heap.
If it's a men heave, this route right here has to be less than the left child and less than the right
child.
So that's what we're talking about.
So let's take a look at a mini example.
So you notice here that five is less than 25 and less than 21.
In fact, five is less than everything, and it's sub trees here, right, because at each level, the
things below it have to be greater than right.
So 25, everything below 25 is greater than greater than 25, right?
So you notice like twenty four to forty one, all these numbers are greater.
Twenty seven.
So that property has to be maintained.
So let's go ahead and watch this part of this -- get built so you can better understand how it works
as far as building a house structurally, what we were talking about, you know, coming from left and
going to the right.
So we're just going to start at this point where it's partially completed.
And let's just say that we insert 48.
We're going to put 48 right here.
Forty two would go right here.
Forty one would go right here.
Fifty two right there, 69 right there.
Seventy seven seventy one.
You notice this just doesn't really matter.
We're just it doesn't really matter what the values are in this situation.
We're just building it out from left to right.
So that's the purpose of showing this, you know, is that you have to build it out like this.
Right.
So unfortunately, though, incoming data is not always going to arrive in a perfect order like that,
you notice that this just like if we're going back, you can see us just building perfectly.
We just we just so happen to be getting all these values that are greater than the parent.
We care about it being a men heap, right?
So they're supposed to be greater than the parent, but we just keep getting like perfect values that
are always like 52 is greater than that.
Oh, in 69 next.
That's great because it's bigger than that.
You know, we come over here.
These are these are all greater.
All of these children that we're putting in are all greater than the parent know that we're attaching
them to your.
So very rarely will the data actually be like that and arrive in that perfect order, so let's see what
a real heap insertion will look like.
So let's say we want to insert tape.
So this is kind of a situation where we're going to do what we did before.
Twenty eight is greater than 25.
We're going to want to put it here, no matter what, because the structural property.
Says that we need to build the heap this way, building it from the left to the right.
So we go ahead and we put twenty eight here what we would do next as we would compare it.
So we would say is 20 less than 25.
No, it's it's not less than 25.
So we don't really have to like worry about doing anything.
The heat property is still satisfied, right?
The mini property here.
So let's say we want to insert three now we know where it's going to go, right?
We just put one right here.
So now we need to put one right here.
That's the next spot.
We go ahead and we put three right there.
Then we say is three less than 25.
Three is less than 25, so we actually need to do something about that.
And what are we going to do?
Well, we're going to swap.
We're going to swap three with twenty five and bring twenty five down here.
So we swap those.
And 25 comes down here.
We're not done yet, though we have to compare it and tell it cannot be basically pushed up anymore.
This is what we would call bubbling up.
So we're taking the value and bubbling it up to the position it belongs in.
So we look at the next parent, right?
Three came up to here.
Twenty five went down.
Now we say, OK, let's check to see if three is less than five.
The parent, right?
Yes, it is.
So we have another situation where it's still listed, so we're going to have to do another swap.
So we swapped three and five here.
Now three is at the top.
So now the heat property is fulfilled, right?
If we look at everything in the heap, we notice that, OK, three children, are they less?
Yeah, five is less.
21 is less.
What about five or 10?
At least it's greater, right?
So three is less than its children, right?
So yeah, five is greater than three.
Twenty one is greater than three.
Five.
Let's look at it's children.
Yeah, twenty eight is greater than five.
Twenty five is carrying the five, so the heat property is satisfied.
The structure is fine.
Everything has been built from the left, so we're looking good.
Let's say that we insert 21.
So this is the next spot.
And just regardless of what the value is, we have to put something here because we're building from
the left to the right.
21 happens to be the same value as the parent.
We go ahead and we check is 21 less than 21.
No, it's not as the same, right?
It's equal.
So we actually don't do anything and we leave it there.
And the heat property is still satisfied because it's a less than or equal to thing, right?
As far as looking at the children, we want the children to be greater than or equal to.
We want the parent to be less than or equal to four men heap, of course, because that's the example
we're covering, right?
So how do we implement a heap?
Do we make nodes and use pointers?
Remember, the binary search tree had a node class and then we kind of had a binary search tree class
where we could have like a left child and a right child right there, the sub trees and stuff like that.
So we were just traversing pointers and creating a data structure on our own.
Like that, right?
So we actually don't have to do that there as hip is so simple that we can just use an array.
And so you might be thinking, well, OK, we have all this stuff in the array, but how do we know
where to put the stuff in there?
Like how does this tree?
Thing translate into an array.
Well, the array is essentially like a flattened version of the tree.
And since the heat property is so simple, right, it's like, you know, we build from left to right
and we also just need to have the children be both less than the parent or if it's a, you know, men
heave, we want the children to both be greater than the parent, right?
So we can actually just mention three kind of properties about the positioning of the elements in the
array to make it heat.
So.
If we say that the index of the left child and so let's say we're talking about some node at position
I so for example, let's take a look at the root node, right?
We noticed that three is the root of this tree right here.
And let's take a look at the array.
Three Is it the first position, right?
So the rule will always be at the first position.
You can always just remember that.
So what is the index of the Route three?
Well, it's zero.
So let's take a look at this property right here.
Index of left child of the node at two eye plus one.
So let's look at the tree.
What is the left child of the three?
It's five, right?
This says two is plus one.
Well, what's eye in this case?
I is the index and zero two times zero plus one is one right?
Zero plus one.
So we get to index one, right?
That's the answer of this right here.
So if you go to index one was there, it's five.
Oh, well, yes.
So it corresponds with the left one.
Let's take a look at this index of right child at two plus two.
So two times zero plus two is two.
What is the right child of three?
It's 21, two times zero plus two is two, we said.
So if we go to index two, it's twenty one.
Well, let's check.
Let's check some other stuff.
So we'll just check the whole tree.
Five.
Right, so left child.
Twenty eight two times.
Five say the it was the index of five.
It's one right.
Two times one plus one is three.
So let's go to index three.
It's twenty eight right.
So there's the left child appropriately stored.
And then what about the right child, so the right child is to two times II plus two eyes, one right
for five, so we have two plus two, that's four.
So we go to index for us, there's 25 that corresponds with the tree as well, and then 21.
Let's just go ahead and look at that.
So 21.
If we look at where that is stored, it's that well, this is this this position right here, we can
look at this, this 21 right here.
We have two ones in here.
But.
If we look at this twenty one right here, if we go to a times two plus one, right?
That's five if you look right here.
Twenty one is the child right?
And we look at index five.
Twenty one is here.
So I just want to walk you through and show you really what it all breaks down to as in putting it in
the array.
So when we flatten this out, the reason why we can use an array is our ability to use these formulas
to be able to access the children.
And it works, vice versa.
You know, the opposite way as well.
The index of the parent can be said to be at the floor, so we'll kind of like round down, right?
Of I minus one, so index minus one divided by two.
So, for example, let's just take a look at like twenty one.
At the very bottom here, so.
Twenty one is the index five, right?
So if we say five minus one, that's four and we do four divided by two.
Well, that divide evenly, right?
So we say four divided by two is two and that gives us twenty one.
Let's take something over here, for example.
So what about this?
Like twenty five, right?
Twenty five, is it for four, minus one is three.
Three divided by two.
We're just going to round that down and say that it goes in one, right?
So if we go to here, if we say that the answer's one, we see that the parent is stored there.
Five.
So pretty cool, right?
So what is all this even useful for?
Like, why would we use a heap over some other data structure?
Well, heaps are really useful for keeping track of the minimum or maximum values in your data collection.
There also is a cool, efficient sorting algorithm that we will look at in a lecture or two in the future,
which is heap sort and that uses a heap.
So also, just in general, most operations on Heap are quite efficient.
We will be looking at the time complexity of certain operations, and you'll notice that most of them
are like, you know, logarithmic or you might have like in log in if you're building an entire heap
or you might just have linear time and or, you know, even constant time as far as finding the maximum
or minimum thing.
So definitely a pretty efficient data structure.
All right.
So that hopefully serves as a decent introduction to heaps.
In the next few lectures, we'll be getting into more specifics.
So we'll be talking about not only how to insert things in the heat, but how to delete things and how
to make sure that the heap stays a heap when you are deleting items.
We'll also talk about heaps sort and also really cool lecture.
Hopefully, we can talk about a quicker, more efficient way to build a heap as well.
All right.
So with that, I'll see you in the next lecture.