1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Not that I know of. That operation makes sense even without that condition (you just need a way to identify the element you are talking about, which could be done e.g. with a pointer or in some other way). $\endgroup$ – D.W. May 2 '18 at 20:37
  • $\begingroup$ IMO it makes little sense to use a PQ to store and move around elements rather than pointers in such case. If i can identify elements in the PQ, it means that they are unique somehow. $\endgroup$ – Alexey May 2 '18 at 20:51
  • 1
    $\begingroup$ ceur-ws.org/Vol-1525/paper-13.pdf $\endgroup$ – HEKTO May 2 '18 at 21:37
  • $\begingroup$ "single occurrence of any element" - based on what? Do you assume that all the elements have a key, which must be unique all over the queue? Can you please clarify? $\endgroup$ – HEKTO May 2 '18 at 21:47
  • $\begingroup$ @D.W., i've realised that it can indeed be more efficient to keep the data associated to the key in this "keyed" priority queue, rather than in a separate key-value store (less search-by-key operations to perform). Maybe i will go with "priority queue with unique keys" or "indexed priority queue"... $\endgroup$ – Alexey May 3 '18 at 18:26
2
$\begingroup$

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.)

$\endgroup$
0
$\begingroup$

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.

$\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.