Hello, and welcome. My name is William and today's data structure is the indexed priority queue. This is going to prove to be a very useful data structure that you wish you would have known a long time ago. So just before we get started, this video builds off concepts from the previous parody videos, which simply go over the basics. Strictly speaking, you can probably get by without watching all those videos as I will be doing a quick recap. But for those of you who want to know, priority queues and full detail, please check out the description for links to those.

So what exactly is an indexed party queue? Well, it's a traditional priority queue variant which on top of having all the regular priority queue operations, also supports quick updates and deletes of key value pairs. One of the big problems that the index party queue solves is being able to quickly look up and dynamically change the values in your priority queue on the fly, which is often very useful. Let's look at an example. Suppose a hospital has a waiting room with n people, which need different levels of attention. Each person in the waiting room has a certain condition that needs to be dealt with.

For instance, Mary is in labor. So she has a priority of nine. A car she has a paper cut, he has a priority of one. James has an arrow in his leg, he has a priority of seven. Now you just stomach hurts, she gets priority of three. Richard has a fractured wrist so his priority is five.

And lastly, Leah also has a stomach that hurts. We want to process these patients by highest priority first. This means the hospital would serve Mary first Followed by James. However, then something happens suppose Nader's stomach condition worsens, and she started vomiting, her priority needs to get a bit to six. Because of this Nadir gets served next, once they're finished with James. During this time, Richard gets impatient and leaves, he goes to another clinic down the street, so he no longer needs to be accounted for.

Further suppose that a car wash goes to take a drink of water slips on the floor, and as a result cracks his head and needs immediate attention. So we increase his priority to 10. Once now he does that with a car wash should be next. And lastly, this is followed by layer. As we saw in the hospital example, it is very important to be able to dynamically update the priority of certain people. The index party queue is a data structure which lets us do this efficiently.

The first step to using an index party queue is to assign index values to all the keys, thus forming a bi directional mapping. We use an index persecutor to track who should get served next in our hospital, we need to assign each person a unique key index value between zero and n non inclusive. Note that this mapping is intended to be bi directional. So I would advise using a bi directional hash table to be able to flip back and forth between the key and its key index. Basically, any operation on the index party q will require the associated key index of a particular key. So you're probably wondering why I'm saying that we need to map keys to indices in the domain zero to n non inclusive.

The reason for this is that typically part of queues are implemented as heaps, which under the hood are actually arrays. So we want to facilitate being able to index into those arrays. This will be become apparent shortly. I will say though, that often and I mean, very often, the keys themselves are already integers in the range zero to n. So there's no need to actually construct this bi directional mapping. It's already there implicitly, however, it is handy to be able to support any type of key such as names, or general objects. We can think of an index party queue as an abstract data type with certain operations we want it to support here are about a dozen or so operations, we want our index particular support.

These are the leading keys, getting the value associated with a key, checking if a key exists in the priority queue, getting the key index with the smallest value, getting smallest value in the index Burcu being able to insert and update key value pairs. And finally, the specialized update operations increase and decrease key which I'll talk about at the end. For all these operations, you need the key index associated with a particular key that you're dealing with. Throughout these slides, I will be denoting the key index simply as the variable KPI to distinguish it from other index values, so keep your eye out for that. And index party queue can be implemented in several ways, some ways with really good time complexities using specialized heap structures. However, we're going to cover the binary heap implementation for simplicity, you will notice that the time complexity for all these operations are either constant or logarithmic, which is really good.

In a traditional party queue. The remove and update operations are linear because we are not maintaining a mapping to the position of where our values exist within the heap. Before we dive into the index priority queue per se, I want to spend a few slides giving a refresher on the traditional party today structure which only supports values not key value pairs like the index barbecue. Still, both data structures are very similar and most people would consider them the same. Although there are key differences in my opinion. Recall that a very common way to represent a binary heap is with an array since every node is indexed sequentially.

If we were to represent the following binary heap as an array, we would get this array of values. If we know the index of note I, we can figure out what its left and right child nodes are by using simple formulas. The left child is two times i plus one and the right child is two times i plus two, assuming Zero Based indices. As an example, what are the children of the node at index four? Well, we can just plug i into the two formulas I just gave you to obtain the indices nine and 10. Of course, you can always run the math backwards and figure out with a parent of given notice.

Both of these are especially useful if you're either walking up or down the tree. Whenever you want to insert a new value into the priority queue, you insert the new value at the insertion position at the bottom right of the binary tree. Suppose we want to insert the value eight, this would violate the heap invariant, so we need to bubble up the value until the invariant is met. So swap nodes five and 12. The heap invariant is still not satisfied. So swap again, swap nodes two and five, and now the tree is balanced.

Now let's review how removals are done in a traditional priority queue. To remove items search for the element you want to remove, and then swap it with the last node, perform the removal and finally bubble up or down the swap value. For this example, suppose we want to remove the node that has the value five, we don't know where the node value five is within the priority queue, so we have to search for it. This is one of the major differences between the priority queue and the index priority queue. So starting out Zero and process each node sequentially until a node with a value of five is found, if any. So we found a node with a value five to actually remove it from the heap, swap it with the rightmost bottom node.

Once this is done, remove node five from the tree. Now the purple node we swapped into five position may not satisfy the heap invariant, so we need to either move it up or down the tree. In this case, since the purple node has the value of one, which is smaller than its children, and we're dealing with a max heap will want to move the node down. That was a quick recap on just about everything you need to know about a traditional part queue. Now let's talk about implementing an indexed priority queue with a binary heap. For the following examples, suppose we're dealing with n people with different priorities that we need to serve.

Perhaps we're prioritizing people For a queue at a hospital, a waiting line in a restaurant or who knows what the main thing is, we'll assume that the values can dynamically change and that we always want to serve the person with the lowest priority to figure out who to serve. Next, we'll use a min indexed party queue to sort by lowest value first. The first step, as mentioned before, is to assign each person a unique index value between zero and N, non inclusive. These are the key index values in the second column beside each person's name. Then I'm going to give each person and initial value to place inside the index party queue. These values will be maintained by the index party queue once inserted, note that the values can be any comparable value you want not only integers as shown here.

This means we can have strings, objects, or whatever type of data we want. If I was to build a min indexed priority queue out of the key value pairs I have in the last slide. This is the heap I would get. Remember that unlike the previous example, we're sorting by smallest value first, since we're dealing with a min heap. If I want to access the value for a given key K, First, you need to figure out what its key indexes. And then you will look up in the values array maintained by the index priority queue.

Here's a good question, What value does the key Bella have in the index party queue? Well, first find Bella's key index value, which is one, then index into the values array at position one to find the corresponding value for the key in the index furniture. So Bella has a value of 15. Awesome. Now we know how to get the value for a particular key in the index printed Q, but how do we get the index of the node for a particular key? To do that, we'll need To maintain some additional information, namely a position map, we can use the tell us the index of a node in the heap for any given key index.

For convenience, I will store the position map as an array called pm inside the priority queue. As an example, let's find out which node represents the key Dylan. First find the key index for Dylan, which happens to be three. Then look up index three in the position map to tell you where Dylan is in the heap. It looks like Dylan is at the node at the index seven highlighted in orange. Now here's a follow up question.

Where is George in the heap? I'll give you a quick moment to figure that out before I give you the answer. All right, so with just about every operation, the first step is to find The key index for the key we care about, which is George, then use the key index to do a lookup inside the position map and find out the node for George, which happens to be node one. Great. Now we know how to look up the node for a given key. But how do we find the key for a given node, this inverse lookup will prove to be a very useful operation.

Say you want to know which key is associated with the root node at index zero, well, you need to be able to do an inverse lookup to figure that out. To do the inverse lookup from node indices, the keys will need to maintain an inverse lookup table. I will denote this lookup table as I am short for inverse map. Let's see if we can figure out which person is represented in the node at index two. To do that, simply do a lookup in the inverse map at index To. This gives us information about which key index is associated with that node.

Knowing the key index enables us to retrieve the actual key by doing a lookup in our bi directional hash table. In this case, the node at position two represents the key Anna. Here's a follow up question to make sure you're still paying attention. Which key is being represented in the note at index position three. Same as before, find the key index through the inverse map, then with the key index, figure out the actual key from the bi directional hash table, we can then conclude that the node at position three represents the key Isaac. What we just covered was how an index party Q is structured internally, and what all the moving parts are.

Now we want to actually do some useful operations with this index party. Such as inserting new key value pairs removing key value pairs based on a key and also updating the value associated with a key. These are all possible and are actually very similar to how you would do it with a regular priority queue insertion is nearly the same except that we have to update the position map pm and the inverse map I am to reflect the movement of the key value pairs. Suppose we want to insert the key marry with a value of two into the priority queue. What we first have to do is assign marry a unique key index value, then we're going to insert the new key value pair at the insertion position. Notice that upon insertion we updated our arrays at index 12 to reflect that the new value was in fact inserted.

Currently the heap invariant is not satisfied since the new node at index 12 has a value less than the one at node five. To resolve this, we're going to swap the newly inserted value upwards until the heap invariant is satisfied swapping nodes, we need to update the position map and the inverse map. by swapping the values of the two nodes we're exchanging the values array does not need to be touched since it gets indexed by the key index value that we get from the map and not the node index per se. It turns out that the heap invariant is still not satisfied, so we need to keep swapping upwards. Let's have a look at some pseudocode for insertions and this snippet the user calling this function needs to provide a valid key index KPI as well as a non null value they want to insert. The first thing I do is store the value associated with the key inside the values array.

Then I update the position map In the inverse map to reflect the fact that a new key value pair has been inserted into the priority queue. Finally, I move the node up the heap until the heap invariant is satisfied. Let's take a closer look at this swim method to see how that happens. Here we are looking at the swim method, you'll notice that it has two supporting functions swap and less swap is simply exchanges to nodes based on index and last determines if node i has a value less than node j. The logic for the swim function is fairly simple. It begins by finding the index of the parent node and walking up the tree.

For every iteration we walk up one layer in the tree. If the index of the current node is not the root node and the value of the current node is less than the parent node, remember that we're dealing with a min heap and want small values to be as high up as possible in our heap to add Actually issue a note exchange simply call the swap function and provide the index of the current node and the parent node, and then update the current node and the parent node index values. I also want to talk about swapping and how that actually occurs. Because it's slightly different than a traditional protocol. And this swap method, we're not actually moving around the values in the array, we're only swapping around index values. Remember that the values array is indexed by the key index, not the note index.

So effectively, the values array can remain constant while we update the inverse map and the position map. First, we update the positions of where key index values are found in the index persecute, remember what the position map is, it is the position of which node index a given key index is found at. So we can do a straightforward swap by indexing into the inverse map to find the key index value. And swap indices i and j followed by this simply update the key index values associated with nodes iMj in inverse map to do this, this is just a simple straightforward exchange. Next up, I want to talk about polling and removing elements from an indexed priority queue polling is still a logarithmic operation. However, removing is improved from a linear time complexity to a logarithmic time complexity.

Since node position lookups are now constant time but repositioning the nodes after a removal to satisfy the heap invariant is still live with me. So let's jump into an example. Suppose we want to pull the root node This is something we often want to do since it'll give us the key value pair the lowest value in the heap. The first step is to exchange the root node with the bottom right node. As we do that, remember to swap the index values. Now we can remove the red node from the tree.

As we remove the value, let's make sure we store the key value pair we're removing so we can return it from our function later, then clean up the Remove node. Finally restore the heap invariant by moving the swapped purple node down. Since the left and the right child nodes have an equal value of two, let's default to selecting the left one. Let's do a slightly more involved removal by removing a specific key from the index printed view. And this example, let's remove the key Laura. The first thing we want to do is get the key index for Laura, which is the key we're working with.

So in this case, the key index is equal to 11. Once we know the key index, we can use that information to locate the node within the heap by looking inside the position map Then swap the node we want to remove. That is the node, which contains the key value pair for Laura and exchange it with the bottom rightmost node. store the key value pair before the actual removal, clean up the Remove node, and finally restore the heap invariant by moving and swapped purple node up or down, we're going to make the purple node move down because it has a large value. All right, let's look at some pseudocode for removing key value pairs. The code is also very short only five lines of implementation and three lines of cleanup.

The first thing to do is exchange the position of the node we want to remove and the bottom right most node, which is always at index position, as Zed short for size of the heap. Once we've exchanged the nodes, the rightmost node is now in the position Where the node we want to remove was, so we need to move it either up or down the heap to satisfy the heap invariant, we don't know which it will be. So we try to move the node up and down hence sink and swim. Lastly, I just cleaned up the values associated the node we want to remove. You can also return the key value pair being removed, but I didn't do that here. Let's take a quick look at the sync method.

So we understand how that works. to sync a node, we want to select the child with the smallest value and defaulting to the left child if there's a tie. In this next block, I tried to update the smallest child to be the right child. But first I need to check if the right child node index is within the size of the heap and its value is actually less than the one of the left node. The stopping condition is if we're outside the size of the heap or we cannot sync the current note any further. Lastly, we want to make sure we swap the current node with whatever was the node with the smallest value.

Lastly, we want to make sure we swap the current node with whichever was the node with the smallest value. The last core operation we want to do on an index priority queue is key value pair updates. Similar to removals updates in a min index binary heap also take logarithmic time due to the constant time lookup to find out where the node is, and the logarithmic time to adjust where the key value pair should appear in the heap. Suppose we want to update the value of the key karlie to now have a value of one. Like every operation, find the key index or the key we want to work with. The key index for Carly happens to be two, then we can use that key index value to update the values array with the new value.

Of course the heap invariant may not be satisfied. So we need to move the node either up or down until it is. The pseudocode for updating the value of a key is super simple. Simply update the value in the values array and move the node either up or down the heap. It's that easy. All right, so there was nothing too special about updates, but the part I really wanted to get to was increase and decrease key.

In many applications such as dextrous or prims algorithm, it's often useful to be able to update a given key to make its value either always smaller or always larger. In the event that a worst value is given to the index pq it should not be updated. In such situations, it is often useful to define the more restrictive form of update operation called Increased key or decreased key respectively, depending on whether you want to increase the value associated with a key or always try and decrease the value associated with a key. Both of these operations are very simple. They simply consist of doing an if statement before performing an update operation, which either increases or decreases the value associated with a key. So bottom line, these two functions are just convenience methods that rapid get operation with an if statement to update a value.

Well, that's all I've got for you on the index priority queue. Let me know if you have any questions. I really do love answering those. And in the next video, I'll be showing you guys some source code for a min index the binary heap. Remember, you can always see the source code on my destructors repository on GitHub. There should also be a link in the description.

As always, thanks for watching. Please, like video if you learn something and subscribe for more mathematics and computer science videos