1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.