Priority Queue Inserting Elements

welcome back today we're going to talk about adding elements to a binary Heap this is part three of five in the priority Q 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 CU Okay so a very popular way to implement a priority que 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 Q however I want to make this clear a priority Q is not a heap a priority Q is an abstract data type that defines the behavior a priority Q should have the Heap just lets us actually Implement that behavior as an example we could use an unordered list to achieve the same behavior we want for a priority q 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 heaps pairing heaps and so on and 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 value is greater than or equal to that of 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 that 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 Tre 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 will 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 very important one last thing before we actually get into how to add values into our 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 very convenient actually because when we're maintaining this complete tree property the insertion position is just the the last position in our array however this isn't the only way we can represent a 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 node 9 which is index zero we're at the top we're at node 8 we're at position one then 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 that way and also another interesting property of storing a binary Heap in an array is that you can a easily access all the children and parent nodes so suppose I is a the index of a parent node then the left child is going to be at index 2 * I + 1 and the right child of that node is going to be at 2 I + 2 this is zero base if it's one base then you would just substract one so suppose we have node 7 which is highlighted in purple well its index is two so by our formula the left child of seven should be located at 2 * 2 + 1 or or five and if we look look at index 5 we expect to get one and if we look at the right child we should expect to get 2 * 2 + 2 or 6 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 our array in the source code I will be presenting in part five of 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 maintain the Heap invariant because if we add nodes to 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 a one which we can see which should actually appear at the root since we're dealing with with a 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 perform what's called bubbling up as my undergrad Prof love to say this is sometimes called swimming or even sifting up all really cool names for really neat operation so we insert one in 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 heat 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 the heat property so we swap and now one is at the route where it should be and now the Heap invariant is satisfied and we 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 four 0 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 in the insertion spot left of all the nodes on its layer and we bubble it up until we can't anymore and we stop the heat property is satisfied next is 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 zero is at the top of the tree next is to insert 10 next number is 10 so we put at the insertion position and have however this does not violate the Heap and variant 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 at the link below and part five of this series we'll be going over the source code in detail um but for now thanks for watching and in the next video we're going to be covering removing elements from a binary Heap very cool hope to see you there