CODEWITHSUNDEEP
c#.netpriority-queue
Phillip Ngan
Phillip Ngan

Reputation: 16126

How to change priority of an element contained in PriorityQueue in C#

Given an element contained in a .NET System.Collections.Generic.PriorityQueue, how does one change its priority value in-place? If this not possible, then should one Dequeue() the item, and Enqueue() it again with the new priority value? I don't see anything obvious in the documentation, but asking in case I've missed the relevant details.

Upvotes: 2

Views: 2874

Answers (2)

Theodor Zoulias
Theodor Zoulias

Reputation: 43738

The PriorityQueue<TElement,TPriority> collection is not updateable. Supporting updates would require maintaining more state, and the enqueue/dequeue operations would become slower, so Microsoft opted for releasing a non-updateable version. There is a proposal on GitHub for adding the update functionality, that you could support by upvoting the proposal:

.NET 9 update: A new Remove API was added in the collection, allowing to search for a specific element in the queue and remove it. The complexity of the Remove is O(n):

public bool Remove (TElement element,
    out TElement removedElement,
    out TPriority priority,
    IEqualityComparer<TElement>? equalityComparer = default);

This new API makes the collection updatetable, albeit inefficiently:

public static bool TryUpdatePriority<TElement, TPriority>(
    this PriorityQueue<TElement, TPriority> source,
    TElement element, TPriority newPriority, out TPriority oldPriority)
{
    ArgumentNullException.ThrowIfNull(source);
    if (source.Remove(element, out TElement removedElement, out oldPriority))
    {
        source.Enqueue(removedElement, newPriority);
        return true;
    }
    return false;
}

Upvotes: 5

Guru Stron
Guru Stron

Reputation: 142833

PriorityQueue is a data structure which needs to store items in certain way to maintain complexity guarantees, so simple inplace replacement should not be possible in general case. You can use Enqueue/Dequeue approach but possibly recreating queue by using UnorderedItemsCollection property (processing in via LINQ and "replacing" needed item) and using EnqueueRange(IEnumerable<ValueTuple<TElement,TPriority>>) can be a faster approach (requires testing, especially with actual data).

Upvotes: 2

Related Questions