[API Proposal]: Add a Remove method to PriorityQueue

[eiriktsarpalis]

Background and motivation

When we shipped the PriorityQueue class back in .NET 6 we made the explicit decision to not add support for efficient, $\mathcal O(\log n)$ priority updates. This was due to priority updates not being supported without sacrificing overall performance and lack of widespread use in .NET codebases. We have a separate issue that tracks adding a separate heap type that does support priority updates.

Even though the PriorityQueue type itself cannot be retrofitted to support efficient priority updates, it can be made to support $\mathcal O(n)$ priority updates. This can be useful in educational contexts or coding interviews, where the actual asymptotic performance is not mission critical and can be overlooked. Put differently, users have asked for this facility so that they can implement Dijkstra's algorithm in leetCode using C#.

In the case of the Java, users can encode priority updates in the PriorityQueue class by piggybacking on its built-in remove method.

API Proposal

namespace System.Collections.Generic;

public partial class PriorityQueue<TElement, TPriority>
{
    // Scans the heap for elements equal to the provided value and removes the first occurrence.
    public bool Remove(TElement element, out TPriority priority, IEqualityComparer<TElement>? equalityComparer = null);
}

API Usage

It's possible to use the above API to encode a $\mathcal O(n)$ priority update as follows:

public static void EnqueueOrUpdate<TElement, TPriority>(this PriorityQueue<TElement, TPriority> queue, TElement element, TPriority priority)
{
    queue.Remove(element, out _);
    queue.Enqueue(element, priority);
}

Alternative Designs

No response

Risks

It could end up being used in production code. I expect this risk would be mitigated since we're not explicitly adding an "update" API, instead users need to invoke a Remove API that will be explicitly documented as a linear-time scan operation.

[ghost]

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

Issue Details

---

Background and motivation

When we shipped the PriorityQueue class back in .NET 6 we made the explicit decision to not add support for efficient, $\mathcal O(\log n)$ priority updates. This was due to priority updates not being supported without sacrificing overall performance and lack of widespread use in .NET codebases. We have a separate issue that tracks adding a separate heap type that does support priority updates.

Even though the PriorityQueue type itself cannot be retrofitted to support efficient priority updates, it can be made to support $\mathcal O(n)$ priority updates. This can be useful in educational contexts or coding interviews, where the actual asymptotic performance is not mission critical and can be overlooked. Put differently, users have asked for this facility so that they can implement Dijkstra's algorithm in leetCode using C#.

In the case of the Java, users can encode priority updates in the PriorityQueue class by piggybacking on its built-in remove method.

API Proposal

namespace System.Collections.Generic;

public partial class PriorityQueue<TElement, TPriority>
{
    // Scans the heap for elements equal to the provided value and removes the first occurrence.
    public bool Remove(TElement element, out TPriority priority, IEqualityComparer<TElement>? equalityComparer = null);
}

API Usage

It's possible to use the above API to encode a $\mathcal O(n)$ priority update as follows:

public static void EnqueueOrUpdate<TElement, TPriority>(this PriorityQueue<TElement, TPriority> queue, TElement element, TPriority priority)
{
    queue.Remove(element, out _);
    queue.Enqueue(element, priority);
}

Alternative Designs

No response

Risks

It could end up being used in production code. I expect this risk would be mitigated since we're not explicitly adding an "update" API, instead users need to invoke a Remove API that will be explicitly documented as a linear-time scan operation.

Author:	eiriktsarpalis
Assignees:	-
Labels:	api-suggestion, area-System.Collections, untriaged
Milestone:	-

[bartonjs]

Video

• We added an out for the removed element to forestall future requests for it.
• We added some nullability annotations.

namespace System.Collections.Generic;

public partial class PriorityQueue<TElement, TPriority>
{
    // Scans the heap for elements equal to the provided value and removes the first occurrence.
    public bool Remove(
        TElement element,
        [MaybeNullWhen(false)] out TElement removedElement,
        [MaybeNullWhen(false)] out TPriority priority,
        IEqualityComparer<TElement>? equalityComparer = null);
}

[ghost]

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

Issue Details

---

Background and motivation

When we shipped the PriorityQueue class back in .NET 6 we made the explicit decision to not add support for efficient, $\mathcal O(\log n)$ priority updates. This was due to priority updates not being supported without sacrificing overall performance and lack of widespread use in .NET codebases. We have a separate issue that tracks adding a separate heap type that does support priority updates.

Even though the PriorityQueue type itself cannot be retrofitted to support efficient priority updates, it can be made to support $\mathcal O(n)$ priority updates. This can be useful in educational contexts or coding interviews, where the actual asymptotic performance is not mission critical and can be overlooked. Put differently, users have asked for this facility so that they can implement Dijkstra's algorithm in leetCode using C#.

In the case of the Java, users can encode priority updates in the PriorityQueue class by piggybacking on its built-in remove method.

API Proposal

namespace System.Collections.Generic;

public partial class PriorityQueue<TElement, TPriority>
{
    // Scans the heap for elements equal to the provided value and removes the first occurrence.
    public bool Remove(TElement element, out TPriority priority, IEqualityComparer<TElement>? equalityComparer = null);
}

API Usage

It's possible to use the above API to encode a $\mathcal O(n)$ priority update as follows:

public static void EnqueueOrUpdate<TElement, TPriority>(this PriorityQueue<TElement, TPriority> queue, TElement element, TPriority priority)
{
    queue.Remove(element, out _);
    queue.Enqueue(element, priority);
}

Alternative Designs

No response

Risks

It could end up being used in production code. I expect this risk would be mitigated since we're not explicitly adding an "update" API, instead users need to invoke a Remove API that will be explicitly documented as a linear-time scan operation.

Author:	eiriktsarpalis
Assignees:	eiriktsarpalis
Labels:	api-approved, area-System.Collections
Milestone:	9.0.0