Hello, and welcome back. Today we're going to look at some source code for an indexed priority queue. So just before we get started, make sure you watch my video on the index party queue, where I go over the implementation details and why an index priority queue is an important data structure. All the source code for this video can be found on my data structures repository@github.com slash Wm for dessert slash data structures the link can be found in the description below. Here we are in the source code for a min indexed binary heap. This source code is presented in the Java programming language.
To get started, notice that our min index binary heap requires that we pass in a type of object which is comparable This is so we can order our key value pairs with Then the heap, you'll also notice that I'm extending a min indexed dairy heap. This is just to be more generic. And all I do in the constructor is simply initialize this heap to have at most two children for each node while at the air heaps supports in general and teach children. So let's look at the D air heap implementation where all the fun stuff is happening. So let's go over I guess all the instance variables. So s, Zed is just the number of elements in the heap and as a constant, representing the maximum number of elements in the heap, D is the degree of each node.
So for the binary heap, this number is two. The two arrays, child and parent track the child and parent indices for each node, so we don't have to compute them dynamically. pm and I am or the position map and the inverse maps which we're going to use to track The key indices for our keys. And lastly is the values array, which is the array that contains the values associated with a certain keys. Note that it's very important to notice that this array is indexed by the key indices and not by the nodes, indices per se. So in the constructor, we give a degree and a certain maximum size for our heap.
Then we just initialize whatever value for the degree and the maximum size of the heap. Then I initialize all our arrays, and I compute what the child and the parent indices should be. And I also initialize the position map and inverse map to have all negative one values. Then we have a few straightforward methods such as size is empty, contains. So you'll notice that for contains, we don't pass in the key for our key value pair instead we pass in the key index. And we're going to do this for all our methods.
So I just have a few convenience bounds checking methods that you'll see again, throughout these videos such as key has to be in the bounds or throw. So this just makes sure that the key index is valid. And after this check is done, we can check does that key exist within our heap by looking inside the position map and checking that the value is not equal to negative one. Then we have things like peak min key index, which gets the key index or the node at top of the heap. And similarly pole min key index and also peak min value and pull min value. The reason these are separate is because sometimes we want to just look at the value at the top of the heap but not necessarily remove it, the pole version will actually remove it.
Now let's look at insert So to insert a key value pair, we need to make sure that that key value pair does not already exist in the heap. Otherwise, we're going to throw an exception that I simply validate the values not know. And if it is we throw an exception. Otherwise, we simply update our indices for the position map and inverse map, then we assign the values array to have the value we passed in, and then we swim up that node, which we know will be at position size, and we also increment the size variable so that our heap is one element larger than the value of pretty straightforward just do a lookup inside the values array. then delete is slightly more interesting. We make sure the key exists, then we get the index of where that key exists within the heap.
We swap the index of the node and the last node in the heap then we reposition the new node. We Walked into AI's position to go either up the heap or down the heap, we capture the value in the position for the key index so that we can return later, we clean up the node we want to delete. And finally we return that value. update is also pretty easy. Just make sure that the key exists and the value is not no, then we get the index for the node, then we capture the old value, update the new value and move it within the heap and finally return the old value. So increase and decrease are just short for decreased key and increased key.
We're dealing with a min dear heap here. So make sure you take that into account when looking at the logic so we make sure the key exists and it's not know that if the value is less than the value already in the heap, the values array at the key index, we can update it and also swim it down. Notice that it didn't call the up method here because we know we're going to swim down in the update method, we sink and we swim. So we do both operations, we don't know which way the node will go, whether it's gonna bubble up or bubble down. But in the decrease key method, we do, same thing for the increase key method, except I switched the order for the last competitor so that the values array x and the first position and the value being passed in is on the right.
These are just the sink and swim methods I talked about in the slides, we can go over quickly. So to sync node i, we get the minimum child of node i, since we're working with a DA reheat me to search all the children of the node, find the one with the least value, this is going to be node j, and then we swap i and j. Make sure that i is equal to the value of j and then we find the minimum child again and then repeat this until we can't sink the node anymore. Same thing for swim Except that we need to find the parent of note, I wish we can just do a lookup in the parents array at index, I swap with the parent and keep doing this until i is less than the parent min child just looks at all the children of node Li and finds the one with a minimum value and returns its index.
Also pretty straightforward. Swap, we covered this in the slides basically swap the indices in that position map in the inverse map for nodes i and j. Then we have the last function which simply compares values, the values for notes, iMj and other convenience methods just because I didn't want to include all the logic of throwing exceptions everywhere and just kind of wrap them in helper functions. This is just for tests to make sure that our heap isn't these a min heap. So that's all there is to and indexed the air. He I hope there wasn't too much to ingest.
And thank you for watching. Please give this video thumbs up if you learn something and subscribe for more mathematics and computer science videos.