Indexed Priority Queue change key

Question

So I was just studying about Indexed Priority Queues and I got confused about the increase key operation.

So basically we have the option to increase a key for an element in log n time because we can look up the index using another array that maps keys to indexes. So let's say that 'A', 'B', 'C', 'D', 'E' are mapped with priorities 1,2,3,4,5 respectively. So if I increase the key value of 'B' from 2 to 1, then that will mean updating the keys[1]='B'. But now 'B' is present in two places 1 and 2 which does not seem to be right.

https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html. In this implementation, it is given to update the key assigned to an index. But what we really need to do is change the index of a key isn't it? That is what means changing the priority of an element in the queue. Or did I understand the algorithm wrong? Please correct me If I did.

Answer 1

I think your confusion is due to the fact that you are looking at keys and priorities separately, whereas in the implementation you are referring, they are treated as one. That is, keys are expected to be drawn from some ordered set (they are required to be Comparable in the implementation ) and their precedence from the set they are drawn define their priorities.

Consider your example K =['A','B','C','D','E']. We assume for the moment that their priorities are based on how they are arranged lexicographically and not based on how you define it in your example . It is important to note here that keys are expected to have indexes prior to inserting them in the priority queue. We achieve this by storing them first in an array, but this is not necessary and you can use whatever means possible to map keys to indices. Now, adding each key to the priority queue is done as insert(i, K[i]), for $0 \leq i \leq 4$. This is equivalent to assigning to each index $i$ a priority $K[i]$. That is why you observed that the update key changes the assigned key to an index.

I believe what you want is to treat each entries of $K$ as some ordinary element and not as keys, hence not as priorities. You define priorities of the elements using another array $P = [1,2,3, 4,5]$ such that the correspondence between elements and priorities is based on their indices. The proper way to store this in the indexed priority queue is insert(i, P[i]). To update the priority of an element to $p$, say the priority of 'B', you perform increaseKey(1,p) since the index of 'B' in $K$ is 1.

As a final note, observe that to be able to update the priority of an element, you must be able to find its index in $K$. To efficiently perform such queuries, you might want to use a Map to represent $K$ instead of an ordinary array.

Answer 2

In a usual priority queue, you insert items, and you delete the top item. To change a key, the obvious way would be to remove the item, change the key, and insert the item back. The problem is: You don’t know where the item is in your heap. And searching would be O(n) for n items in the priority queue.

Since you know the location of the item, you can remove and re-insert it. Both operation obviously need t be done carefully; other items will be moved and you keep track of these changes. And finally you change the location of the item whose key you changed.

If you say “increment the key” it seems the change in the key is small, so the item would be close to or even in its correct location. Since you know the location of the item, you can start at the top and for the new key you follow the path to the old key as far as possible, minimising the work to be done.