Correct term for a priority queue with unique elements 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.
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.)