Priority Queue Code

all right welcome back everybody this is part five5 in the priority Q Series and we're going to have a look at some source code for the priority que today so if you want the source code here's a GitHub link with all the data structures in the series the priority que is one of them also make sure you've watched Parts one to four so you can actually understand what's going on all right let's dive into the code all right here we are inside the source code so notice that inside my priority Q the types of elements I'm allowing inside my priority Q have to be comparable elements as we talked about so if they implement the comparable interface then we are going to allow them inside our que so this is anything like strings integers anything with a comparable interface so let's have a look at some of the instance variables so I have the Heap size so this is the number of elements currently inside the Heap but then I also have another instance variable which is the Heap capacity so this is going to be the size of the list that we have for our Elements which may be larger than uh the Heap size is and this is the actual Heap and we're going to be maintaining it as a dynamic list of elements ments using Java's list next for our log of and removals I'm also going to keep track of this map it's going to map an element to a tree set of integers so these are going to be all the positions inside our Heap which we can find this element T all right next I've got a few different Constructors for our priority queue uh we can just create a priority queue and by default I'm creating an initially empty priority Q with a capacity of one but I also allow you to create a priority queue with a defined initial capacity which actually is more useful because then we don't have to keep expanding our Dynamic list every time so I would recommend this but also even better is if you know all the elements that are going to be inside your HEAP you can actually construct the priority Que in linear time using an operation called heapify which I didn't talk about in the slides but but it can be very very useful so so this just has all the usual setup stuff um here I'm adding all the elements to the map but also to the Heap and then here's the heapify process so we start at um about halfway through the Heap size and then we start decreasing and then we sync all the elements and you're like wait a second isn't this seek uh sync a logarithmic removal well yes it is in the general case but not if we're doing it in this fashion um I put a link this paper up here just because uh the heapify operation isn't quite intuitive why it has this uh linear complexity and if you look at the analysis in the paper you you'll end up seeing that um the complexity boils down to a convergent series and that's why we get a constant and we can say it's linear time but in general this isn't what you might be tempted to do if you're giving a collection of elements um you would initialize the Heap and then you would just use our add method to add the elements one at a time and this will give you an end log and bound but uh definitely use the heapify whenever possible okay now some pretty simple methods we have is empty just returns true or false if the Heap is empty or not then clear so when we clear the Heap we remove all the elements inside our Heap array but also so inside our uh map so that's why I call map. CLE size returns a size it's pretty simple um Peak the first really useful method just looks at the top of our uh prior priority q and if it's empty returns null otherwise we do a look up at the first index inside our uh Heap and return it because it's the root node pole uh similar to Peak except that we're going to uh REM remove the very first element and we're also going to return it because we want that information next contains so because we have a map with all our elements we can do a uh map look up to see if our elements inside the Heap and this reduces our complex from uh linear in which case we have to scan do a linear scan through elements to check containment to constant time which is remarkable um but in the general case people don't usually maintain this map I I just wanted to do it just to show you guys that it is possible although the map does add a lot of constant overhead you may or may not want um I personally find that the overhead is quite a lot and I usually don't really remove things very frequently from Maps so it might not be entirely worth it but it's up to you if you're doing as many additions as you are uh removals then definitely worth it all right now let's have a look at the ad method uh so so this element sorry this method adds an element to the prior q and that element cannot be null so what we do is first we check if um our Heap size is less than capacity otherwise we have to uh expand our capacity of the Heap next we make sure we add it to the map so we keep track of it and then we uh swim it up remember that we have to swim a node up because we add it to the very end of our list and so we have to like adjust where it goes inside our Heap by swimming upwards this next method called less is is a helper method which helps me check if node I is less than or equal to node J and this uses the fact that both elements node one and node two are comparable so we can invoke the compare to Method um if we go back up that comes from this interface the comparable interface which we needed so let's scroll back down all right so it returns true if I is less than or equal to J awesome so next this is the bottom up node swim so we are going to try to swim node K so first we grab the parent of node K and we can do that by uh solving for the parent so remember that I'm working in uh I'm starting at zero some people like to start their heaps index at one I like everything zerob based so I get the parent um which is at this position kus1 / 2 because we're going upwards and and uh while K is still greater than zero so we're not at the root and we are less than our parent then we want to swim upwards so we're going to swap the nodes parent and K and then K is going to become the new parent and then we have to get the parent of K once more and then we keep doing this going up our Heap and swapping notes so that's how we do the swim so the sync is similar but a little different so this a top down node sync and here we want to sync node K and what we do is I grab the left node but I also grab the right node remember we're working zerob based so plus one plus two instead of um plus 0 and plus one and then I need to figure out which is uh less either it's going to be the left one or the right one and I assume to start with that the left one is going to be smaller than the right one and here I correct that hypothesis in case it was false so I check that the right node is within the size of the Heap and if the right node is less than the left node then the smallest one is going to be the right note and our St in condition is that uh we are outside the bounds of the tree or we can't syn [Music] anymore and we kind of do a similar thing we swap and then K is the next smallest kind like like we did in um uh the last method also so the swap method I I made a an explicit method to swap because I also have to uh swap things inside the MTH and then uh set the values also and this is really what adds a lot of the overhead for the map is the fact that every time we call the swap method we also have to swap things inside the map which which can be a lot of overhead really it technically maps are constant lookup times but the fact that you're doing all this internal hashing and and collisions and whatnot it can get costly so remove so if the element is null uh return false so we know we don't have any null elements inside our Heap so this is how you would do a uh linear removal in linear time I commented out in case you want to revert back and remove the map and whatnot uh is you would scan through all the elements and once you find the element you were looking for um just remove it at that index and return true otherwise uh we're going to use our map so get the index of wherever the element one of the elements are um and if it exists then remove it at the index okay now let's have a look at the remove at method so this is what I covered in the last video so if our Heap is empty well can't really remove anything otherwise we going to swap the index of what we want to remove with the last element which is going to be at uh Heap size and then we are going to kill off uh that node and also remove it from our map so if it so happened that um I was equal to the Heap size meaning we just removed the the very last element in our Heap just remove uh return the removed data otherwise when we did the swap we have to either sync that node up or down and uh I'm kind of too lazy to check whether I need to sync or Swim so I just try both so first I try syncing and then uh if nothing happened then I I try uh swimming downwards and in either case return the remove data perfect so this just readjusts where um where the swap node position goes either Bubble Up or bubble down this method is just a method I use in my testing framework to make sure everything is uh good so it checks essentially the Integrity of the minimum Heap so initially you call this method with k equal Z and that starts at the root and it's going to recursively go down the tree and check are we maintaining the Heap invariant property which we need so uh our basee is going to be that K is outside the Heap size uh and if so we're just going to return true otherwise get our children left and right and now we're going to make sure that K is less than uh both our children and if that's not the case we turn false and if we ever return false because we have an and statement when we're recursing right here um that that gets propagated throughout the recursion and this whole method will return false otherwise if everything returns true and hits the base case then we know for sure it's in minimum Heap okay these last few methods are uh just map helper methods so um things to add things into the map uh things how to remove elements from the map and so on and what I'm doing here is I'm using a tree set to uh add and remove elements because I know the tree set implementation Java is a balance binary search tree so all operations on tree sets are logarithmic um which is really nice so so you guys can have a look at those in more detail it just uh gets values removes values and lastly uh do a map swap so yeah swaps um values in the Heap or in the map rather so you guys can have a look at those in more detail um but I pretty much covered everything about the priority queue so if something's unclear just drop a comment and I'll get back to you as soon as possible but that's the Heap uh sorry the binary Heap implementation uh of a priority queue remember that the source code is on my GitHub repost you have a look at that um so guys thank you for watching and I'll catch you next time