Hi everyone.
In this video let's discuss a new data structure called binary heaps.
Now these are the five things that we will discuss in this video.
First we will discuss what binary heaps are.
Then we will go ahead and take a look at max and min binary heaps.
And then we go on and see how we can store a binary heap as an array.
And finally we take a look at the range of leaves and internal nodes and the Big-O of common operations
for a binary heap.
All right.
So these are the five sections.
Now let's get started with section one and take a look at what binary heaps are.
Now over here we have two words binary and heaps.
Now heaps over here is a tree based data structure.
All right.
And then we have the word binary over here indicating that every node can have at the most two children,
which was similar to the case of a binary tree.
Now when it comes to a binary heap, this is actually a complete binary tree.
All right.
So a binary heap is a complete binary tree.
And this is a concept that we have discussed previously.
Now we have two types of trees in a complete binary tree.
It can either be a perfect binary tree or an almost complete binary tree.
Now again this is not complex right.
It's pretty straightforward.
So if you have nodes you have to keep filling from left to right.
And you cannot skip any position.
Right.
So that's how you make a complete binary tree.
So the next node would be filled over here.
And again if you have more nodes you have to fill from left to right.
So the next node would come over here.
And after this you have to fill over here right.
So again it's pretty straightforward.
You have to keep filling nodes from left to right to get a complete binary tree.
And binary heaps are actually a complete binary tree.
All right.
So the advantage of a binary heap is that it cannot be one sided.
Again remember when we discussed a binary search tree?
One of the downsides is that you could actually have a valid binary search tree or a BST, which is
one sided.
And in that case it would look more like a linked list.
Right now.
Again, there is one more thing.
So a binary heap is a complete binary tree.
This is point number one.
And the second point is that it satisfies the heap property.
All right.
So again in the case of binary search tree we had a property over there.
Similarly in the case of a binary heap there is a heap property.
And a binary heap satisfies the heap property.
So let's go ahead and take a look at and try to understand what this is.
So that brings us to the second point which is max binary heap and min binary heap.
All right.
So again the heap heap property can be of two types.
So if we are discussing a max binary heap this is a tree type of data structure where every parent node
is larger than the child node.
All right.
So that's why you have max over here because it's larger.
And in the case of a min binary heap every parent will be smaller than the child.
So this is the heap property.
And also remember that in the case of a binary heap, there is no ordering between siblings.
So let's take a few examples and try to understand this.
So over here I've drawn out a few binary trees.
You can see that every parent or every node has at the most two children.
Now this binary tree over here is actually a max binary heap.
Now let's take a look at the nodes.
So over here you have 95.
And you can see that this parent is greater than its children right.
So 95 is greater than 50 and 45.
Similarly 50 is greater than one and two and 45 is greater than 30.
And then it's a complete binary tree.
You can see that the nodes are filled from left to right, and we are not skipping any level.
So this is actually a max binary heap.
Now this tree over here is a min binary heap.
All right.
So you can see every parent is less than its child.
So nine is less than 11 and 15.
Similarly 11 is less than 20 and 1920 is less than 24, 15 is less than 23 and 18.
And we are filling from left to right.
So this is actually a min binary heap.
Now when it comes to this binary tree over here, this cannot be a max binary heap because in that case
you can see the greatest value is coming over here.
All right.
And that's not the case over here.
Right.
Seven is not greater than 22 and 19.
So definitely not a max binary heap.
But can this be a min binary heap.
No this is not a min binary heap.
Why is that so.
Because over here you can see that you have 19 and 14 right.
So over here the parent is 19 and this is 14.
So if it was a min binary heap you would have 14 over here because the parent has to be less than the
child.
So this is not a min binary heap.
So this is not a heap.
Uh, this is not a heap at all.
All right.
Now what about this one over here?
This is also not a heap.
Why is that so?
Because it's not complete, right?
This is not a complete binary tree.
Because the nodes have to be filled from left to right.
So that's why this is also not a heap.
And what about this binary tree over here?
This again is not a max binary heap.
Again, it cannot be a min binary heap because over here you can see you have 76, 50 and 40.
Right.
So in the case of a min binary heap the parent has to be less than the children.
So definitely not a min binary heap.
But this is also not a max binary heap because over here you can see you have 50 and 52.
Now the parent should have to be greater than the children if it was a max binary heap.
So this also is not a heap.
So again to summarize over here we have an example of a max binary heap.
And over here we have an example of a min binary heap.
All right.
So we have covered the first two points.
Now let's see how we can represent a binary heap as an array.
Again this is an important point.
Now we could store a binary heap as we did for a binary search tree where we had the node class.
And then we make a node for each value.
So we could do it in this manner.
But then representing a binary heap as an array is easier.
And this is very important to know for many coding interview questions.
So let's go ahead and learn this now.
Now for this I have an example over here.
So you can see that this is a max binary heap.
Every parent is greater than the children.
Now let's say that this binary tree over here is zero indexed.
All right.
So when we say that this is zero indexed what do we mean.
So we start from here with the index zero.
So this is zero.
Then 123456789 1011 1213 and 14.
So this is what we mean with a binary tree being zero indexed.
Now if this is zero indexed and let me make some space over here.
Let's see some relation between the parents and children's index.
All right.
So if you have a node over here and let's say the index of this node is n, then from over here you
can see by taking a look at the pattern its children will have the indices two n plus one and two n
plus two.
All right.
So let's take an example.
Over here you have zero.
Now if you substitute n is equal to zero over here you will get two into zero plus one which is one
and two into zero plus two which is two.
So that's one and two over here.
Let's take another example.
Let's say we take five.
All right.
So if n is equal to five this becomes two into five plus one which is 11.
And that's what you have over here.
And two into five which is ten plus two.
So this becomes 12.
And that's what you have over here.
So you can see that if the parent index is n its children will have the indices two n plus one and two
n plus two.
All right.
Now if you want to go from the child to the parent again there is a relationship.
Let's say the child index is n.
Now you could be either the left child or the right child.
Right now we are just saying that the child index is n.
In this case, the parent index can be found out by doing floor of n minus one by two.
Again let's take an example.
Let's say we have 11 over here.
And we want to find the index of its parent.
So what do we do.
We do 11 minus one by two.
That's ten by two which is five.
And you can see that the parent index is five.
Similarly if you were starting at 12 now 12 minus one gives you 11, 11 by two gives you 5.5.
And when you floor it you will again get five.
So you can go from the child to the parent by doing floor of n minus one by two, where n is the index
of the child.
Or you can go from the parent to the.
If n is the index of the parent, you just have to do two n plus one and two n plus two.
Now this is something very important that you should know.
All right.
Now using this relationship we will see how we can store this binary heap over here as an array.
So again let's just write the array over here.
So you have 9550, 45, 2122 etc. up to 33.
Again we have just written it down as per these indices.
Right.
So that's what we said, that this binary tree over here is zero index.
So let's write the indices of this array over here 0 to 14.
You can see over here 95 as index zero.
And that's where this 95 is placed at.
For example this 30 is at index five.
And at index five you can see you have the value 30 etc. or at index 13 you have 34.
And you can see that's where 34 is placed.
All right.
So we can store this binary heap over here as this array.
And you can see the indices are marked over here.
All right.
And then it's important to be able to derive the parent and child relationship.
And for that we will make use of this relationship which we have discussed.
All right.
Now again let's take an example and uh, just get familiarized with this.
Now in this array, if I want to find the children of 21, for example, what do I have to do?
I have to take the index of 21, which is three, and then I have to do two and plus one and two and
plus two.
So that would be two into three plus one which gives me seven.
And I also get two into three plus two which gives me eight.
So you can see that the children of index three are at index seven and eight.
And over here you can see that's actually true right.
You have three over here.
And the children are seven and eight.
Indices seven and eight.
And the values are 19 and 20.
Now what if you wanted to find the let's say parent of 16.
So you have this 16 over here.
You want to find its parent again from this array over here.
You can do that without drawing the binary tree over here.
You just need to take its index which is ten.
And then you have to do ten minus one which is nine.
Nine by two gives you 4.5.
And if you floor it you will get four.
So four should be the parent of ten.
So let's take a look whether that's correct.
So you have ten over here.
And you can see the parent is four.
So that's how we represent a binary heap as an array.
And this relationship helps us to identify the parent child relationship.
All right.
Now finally let's go.
Go ahead and take a look at the range of leafs and internal nodes in a binary heap.
Now for this we will make use of something that we've already discussed.
But let's quickly mention it over here as well.
Remember, a binary heap is a complete binary tree.
And we have discussed that in the case of a complete binary tree previously, you can refer to that
video where uh, it's in, it's under the section for Binary Tree.
The range of the leaves will be floor of n by two to n minus one, and the range for the internal nodes
will be zero to floor of n by two minus one, where n is the total number of uh values or nodes right
in the binary tree.
Now let's try to take a look at this formula with the array which we have.
So this is how we represented the binary heap previously.
Now let's write the indices.
So we have the indices from 0 to 14.
So that means there are a total of 15 nodes or values right in this binary tree.
So n is equal to 15.
Now if we find out floor of n by two that would be floor of 15 by two which is floor of 7.5 which is
seven.
Right.
So again over here we know that the leaves are from seven to n minus one, which is 14, and the internal
nodes are from 0 to 7.
This will be seven seven minus one is six right.
So 0 to 6.
These are the internal nodes and 7 to 14.
These are the leaves.
Right.
And again if you take a look at the structure which we have drawn previously, you can see that this
is actually true.
Right.
You have leafs starting at nine at index seven.
Right.
So that's index seven over here.
And 7 to 14 are leafs which is correct.
And then 0 to 6 which are these indices are the internal nodes.
So that's actually correct.
Right.
So you can see that using this relationship we can actually play around with this tree without drawing
it.
Right.
So we can store this as an array.
And again the relationship between the parent and the child is stored in this array itself.
Because we know this relationship that if you have the parent, you can find the child by doing two
n plus one and two n plus two.
And from the child, if you want to go to the parent, all you have to do is just find floor of n minus
one by two.
And if you want to find the leafs then you can do floor of n by two to n minus one again n over here
is the total number of values and for internal nodes the indices range from zero to floor of n by two
minus one.
Again, let's take an example to get more familiarized.
Over here you have node nine.
All right.
Now if you want to find its parent what do you need to do.
You have to do floor of n minus one by two which is nine minus one by two which gives you four.
Right.
So you can see four is the parent of index nine.
And that's true.
You have four over here and you have nine over here.
Again let's practice a little bit more.
If you want to find the children of the value 21 which is at index three, you have to do just.
One plus one and two.
One plus two.
Right.
So that's two into three plus one and two into three plus two.
And that gives you seven and eight.
And you can see that's actually true.
You have three over here.
And you have seven and eight over here.
All right.
So we have seen how we can actually store a binary heap as an array.
We have seen how you can go from an index and find its children and from an index and find its parent.
So that's actually what we want actually.
That's the relationship when we want to store a binary heap.
And if we can get that relationship just from an array, then there's no nothing wrong in storing the
binary heap just as an array.
And we've also seen how we can find the range of the indices for the internal nodes and for the leafs.
And this will be much useful where we heapify something and we will discuss that in the in a future
video.
All right.
Now let's go to the final part where we quickly discuss the big O of common operations for a binary
heap.
Now over here, we are not going to discuss this in detail, because there is a separate video where
we discuss that in detail.
But over here I'm just listing it down for the sake of completeness.
Now, removing and inserting into a binary heap is a O of log n operation.
All right.
And the space complexity is O of one.
Now this is discussed in detail in a future video.
But then just to develop an intuition, remember, uh, a binary heap is a complete binary tree.
And because it's balanced, because it's balanced, the maximum depth or the height of the tree will
be of the order of log n, right?
That would be log n, where n is the total number of values.
So we have discussed that also in a previous video.
And then for inserting or removing at the worst case we just need to make one comparison per one level.
And the total number of levels will be log n.
So that's why for removal or insertion the time complexity is O of log n.
And then I've written down bubble down and bubble up over here again.
Don't worry about it.
We'll discuss that in detail in the next video.
All right.
Now there you can see that when you insert into a binary heap, you make use of something called bubble
up.
And when you remove from a binary heap, you make use of something called bubble down.
So that's why removal or bubble down is an O of log n time operation and insertion or bubbling up is
a O of log n time operation.
Now, searching in a binary heap is in the worst case O of n time complexity.
That's because there is no ordering between siblings, right?
So in the worst case, we'll have to search every element in the binary heap and building a heap from
an array.
Again, this also is discussed in a future video in detail.
That's a O of n time complexity operation.
Now there is a proof of this which we discuss in detail in a future video.