Welcome back. Today we're going to talk about adding elements to a binary heap. This is part three of five in the priority queue series. We'll get to adding elements to our binary heap shortly. But first, there's some important terminology and concepts leading to that, which we need to go over prior to add elements effectively to our priority queue. Okay, so a very popular way to implement a priority queue is to use some kind of heap.

This is because heaps are the data structure, which give us the best possible time complexity for the operations we need to perform with a priority queue. However, I want to make this clear, a priority queue is not a heap. A priority queue is an abstract data type that defines the behavior or priority queue should have the heap just lets us actually actually implement that behavior. As an example, we could use an unordered list to achieve the same behavior we want for a priority queue. But this would not give us the best possible time complexity. So concerning heaps, there are many different types of heaps including binary heaps Fibonacci heaps, binomial heap, pairing heaps and so on, so on.

But for simplicity, we're just going to use the binary heap. A binary heap is a binary tree that supports the heap invariant. In a binary tree, every node has exactly two children. So the following structure is a binary heap which satisfies the heap property that every parent's value is greater than or equal to the child that every node has exactly two children. Well, no, you may be thinking the bottom nodes, also known as leafs don't have children. Well, actually Yes, they do.

Here they are. They're the null children in gray. But for simplicity, I won't draw those because they're annoying to draw. Okay. The next important bit of terminology, we need to understand is the complete binary tree property. The complete binary tree property means that at every level, except possibly the last is completely filled.

And then all the nodes are as far left as possible in the binary tree. As you will see, when we insert nodes, we always insert them at the bottom row as far left to meet this complete binary tree property, maintaining the complete binary tree property is very, very important, because it gives us an insertion point, no matter what the heap looks like or what values are in it. The next node we insert will go into the hollow circle that and the next one, we'll go to the right of it, and so on until eventually we fill up the row at which point we need to start a new row. So the insertion point is a very important one last thing before we actually get into how to add values into a binary heap is we need to understand how to represent one of these binary heaps and there is a canonical way of doing this which is to use an array actually.

So using an array is a very convenient actually, because when we're maintaining this complete tree property The insertion position is just the last position in our array. However, this isn't the only way we can represent the heap, we can also represent a heap using objects and pointers and recursively, add and remove nodes as needed. But the array construction is very elegant, and also very, very fast. So on the left is the index tree just to help you visualize the position of each node in the array. And on the right is the actual tree remark that as you read elements in the array from left to right, it's as though you're pacing through the heap, one layer at a time. So if we're at no nine, which is index zero, where the top for node eight, we're at position one, and as I keep moving along, you can see that we're just pacing through the array going from left to right.

So it's very convenient to that way. And also another interesting property of storing a binary heap in an array is that you can easily access all the children and parent nodes. So suppose high is the index of a parent node, then the left child is going to be at index two times i plus one, and the right child of that node is going to be at two i plus two. This is zero base. If it's one base, then you would just subtract one. So suppose we have a node seven, which is highlighted in purple.

Well, its index is two. So by our formula, the left child of seven should be located at two times two, plus one or, or five. If we look at at index five, we expect to get one. And if we look at the right child, we should expect to get two times two plus two or six. If we look in our array, this gives us the value of two. So using this technique, we have all we need to manipulate the nodes in our array in the source code I will be presenting in Part Five for the series, we will see that I use this representation for simplicity.

All right. So now we want to know how do I add nodes to a binary heap and to maintain the heap invariant? Because if we I noticed our binary tree and we don't maintain the heap property? Well, the binary heap is useless. We'll do some examples. On the left I have some instructions which tell us what values we need to insert into the heap.

The first value is the one which we can see which should actually appear at the root since we're dealing with them Min heap. But instead of inserting one at the root directly, what we do is we put one at the bottom left of the tree in the insertion position I was talking about and performance called bubbling up as my undergrad prof love to say, this is sometimes called swimming or even sifting up all really cool names for a really neat operation. So we answered one and the insertion position. But now we're in violation of the heap invariant since one is less than seven, but one is found below seven. So what do we do? What we do is we swap one and seven, like so.

But now we're still in violation of the heap property, since one is a child of six, but one is less than six. So what do we do we swap them but yet again, violation of property so we swap and now one is at the root where it should be. And now the heap invariant to satisfy and you can stop swimming or bubbling up or whatever you want to call it. So the next one is 13. So as usual, begin by putting it in the insertion position. And now we need to satisfy the heap invariant.

So bubble up 13. Notice that we're no longer in violation of the heat property since 14 is less than 13, and 13 is less than 12. So 13 is actually in its correct position. Sometimes we don't have to bubble up our elements that much. The next values we need to insert are for zero and 10. Try seeing where these end up, pause the video if you need, it's a good little exercise, but I will keep going for now.

So four goes into the insertion spot left of all the nodes on Slayer and we bubble it up until we can't anymore We start with the heat property satisfy. Next zero, my favorite number. Of course, I've arranged that zero be at the top of the tree, as you will see. So right now we're in violation of the heap invariant. So let us bubble up and like magic zeros at the top of the tree. Next is to insert 10.

Next numbers 10. So we put that insertion position. And however this does not violate the heap invariant, so we do nothing. Okay, guys, thank you so much for watching. If you're interested in actual implementation of how to add elements, I've provided some source code, you can look at the link below. And part five of this series.

We'll be going over the source code in detail. But for now, thanks for watching, and in the next video, we're going to be covering removing elements from it binary heap. Very cool. Hope to see you there.