Why doesn't PriorityQueue have the Remove(TElement element) method

[sw47]

The current PriorityQueue Implementation for .NET PriorityQueue Implementation for .NET does not have the Remove(TElement element) method as written on the original contract defined in this #14032

I perused the history of #14032 spanning half a decade+ worth of discussions (!) and unfortunately didn't find the post which proposed to remove the the Remove method from the final implementation.

Can someone shed some light on this? I would have expected the .NET Priority Queue implementation to have a certain degree of parity to [Java's implementation] (https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html)

Also, +💯 this #14032 (comment) - would be great if the history of this API was written up as a blog entry on DevDiv :)

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

The current PriorityQueue Implementation for .NET PriorityQueue Implementation for .NET does not have the Remove(TElement element) method as written on the original contract defined in this #14032

I perused the history of #14032 spanning half a decade+ worth of discussions (!) and unfortunately didn't find the post which proposed to remove the the Remove method from the final implementation.

Can someone shed some light on this? I would have expected the .NET Priority Queue implementation to have a certain degree of parity to [Java's implementation] (https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html)

Also, +💯 this #14032 (comment) - would be great if the history of this API was written up as a blog entry on DevDiv :)

Author:	sw47
Assignees:	-
Labels:	area-System.Collections, untriaged
Milestone:	-

[Joe4evr]

The Priority Queue was implemented according to the API proposed at #43957, which states:

• Should we include a void Remove(TElement element); method?
  • No. Can be ambiguous operation in the presence of duplicate elements.

[sw47]

Thanks @Joe4evr - what was the design rationale for not allowing duplicates? PriorityQueues in Java allow duplicates....

[jnyrup]

PriorityQueue supports enqueuing duplicates, the ambiguity comes when removing.

var pq = new PriorityQueue<int, int>();
pq.Enqueue(1, 1);
pq.Enqueue(1, 2);
// pq.Remove(1); <-- which of the above should be removed?

[Genbox]

which of the above should be removed?

Presumably the one where the equality comparer determines equality. Sure, the default comparer for integer means that 1 equals 1, but in collections, 1 is not an integer - it is a key - and keys do not necessarily have value equality.

Since .NET has a very simplistic equality comparer interface where it is only possible to compare keys and not position/key hash/priority/value, it gives the developer some difficult decisions with potential side effects when it comes to duplicates. Therefore I agree that it is not exactly straightforward, but also not an issue that the data structure necessarily should concern itself with.

However, it makes me think that a RemoveAt() method would be suitable and is a paradigm in .NET collections already. Was RemoveAt() discussed before?

[theodorzoulias]

This issue might be a duplicate of this: Add a priority queue that supports priority updates

[eiriktsarpalis]

It might be worth pointing out that the Remove method in Java's PriorityQueue is an O(n) operation, so using it to express priority updates (as is sometimes recommended in public forums) can be prohibitively expensive. If we do offer such a solution we might consider offering O(log n) operations, but that requires a different implementation: #44871

Closing in favor of #44871.