Correct term for a priority queue with unique elements

Question

Is there a standard term for a priority queue which can only hold a single occurrence of any element? This would be a priority queue for which operations such as "raise the priority of element x to the new value p" would make sense.

In this kind of an abstract container, if you insert some element ("key", but not in the sense of "priority key") with some priority, you cannot insert it again until it is extracted, but you can update its priority.

I would also like to know if there is some established interface for this kind of a priority queues.

Answer 1

I don't know of a name for the abstract data structure.

There is a well-established implementation of what you describe, though: treaps, a combination of BST and heap (i.e. priority queue). This is with priority and value/key being different things, though.

If priority and value are the same, use any priority queue and add uniqueness, i.e. by combining it with a set/dictionary data structure. (Treaps degenerate to sorted lists in this case.)

Answer 2

Does PriorityQueueSet sounds good? A sample signature of Java implementation

/**

• A priority queue that also maintains a set of unique entries.
• @param type of the key to identify the entry
• @param type of the entry
• keyExtractor is used to extract the key from the entry
• valueComparator is used to sort the entries in the queue

*/

public class PriorityQueueSet<K, V> extends PriorityQueue

Answer 3

Let me clarify first that by "unique elements" I meant elements unique by their identities, not by their "values." (In case of mutable objects, distinct mutable objects may at some moment have identical "values.") The identities of elements have to be maintained while the elements are being moving inside the priority queue implementation.

I've decided to go with indexed priority queue.

It turns out that a similar term is used in Algorithms textbook by Robert Sedgewick and Kevin Wayne: they call it index priority queue.

I've also checked out Algorithm Design by Jon Kleinberg et Éva Tardos and Introduction to Algorithms by Cormen et al, but they do not use any special term for this kind of a PQ, and just keep calling it a priority queue.