如何在 C# 中更改 PriorityQueue 中包含的元素的优先级

Question

给定 .NET

System.Collections.Generic.PriorityQueue

中包含的元素，如何就地更改其优先级值？如果这不可能，那么是否应该

Dequeue()

该项目，然后使用新的优先级值再次

Enqueue()

？我在文档中没有看到任何明显的内容，但请询问以防我错过了相关细节。

Answer 1

PriorityQueue<TElement,TPriority>

集合不可更新。支持更新需要维护更多状态，并且入队/出队操作会变得更慢，因此微软选择发布不可更新的版本。 GitHub 上有一个添加更新功能的提案，您可以通过投票支持该提案：

• 添加支持优先级更新的优先级队列

---

.NET 9 更新： 集合中添加了新的

Remove

API，允许搜索队列中的特定元素并将其删除。

Remove

的复杂度是 O(n):

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

这个新的 API 使集合可以更新，尽管效率低下：

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;
}

Answer 2

PriorityQueue

是一种数据结构，需要以某种方式存储项目以维持复杂性保证，因此在一般情况下简单的就地替换是不可能的。您可以使用

Enqueue

/

Dequeue

方法，但可能通过使用

UnorderedItemsCollection

属性重新创建队列（通过 LINQ 进行处理并“替换”所需的项目），并且使用

EnqueueRange(IEnumerable<ValueTuple<TElement,TPriority>>)

可能是一种更快的方法（需要测试，尤其是在实际情况下）数据）。