C# PriorityQueue<TElement, TPriority>优先级队列用法示例

2024-12-26 C# PriorityQueue 87 0

在 C# 中，PriorityQueue<TElement, TPriority> 是 .NET 提供的优先级队列实现，它允许按指定的优先级顺序处理队列中的元素。以下是它的用法示例和详细解释。

PriorityQueue 核心功能

按优先级排序：基于提供的 TPriority 值，队列中的元素以从最低到最高优先级的顺序排列。

泛型支持：支持任意类型的元素和优先级。

动态调整：插入和移除操作会动态调整优先级。

PriorityQueue 基本语法

PriorityQueue<TElement, TPriority>

TElement：队列中存储的元素类型。
TPriority：优先级类型，用于比较和排序。

PriorityQueue 用法示例

1. 基本示例

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 创建优先级队列
        var priorityQueue = new PriorityQueue<string, int>();

        // 添加元素（元素, 优先级）
        priorityQueue.Enqueue("Task A", 3); // 优先级 3
        priorityQueue.Enqueue("Task B", 1); // 优先级 1
        priorityQueue.Enqueue("Task C", 2); // 优先级 2

        // 按优先级取出元素
        while (priorityQueue.Count > 0)
        {
            var task = priorityQueue.Dequeue(); // 取出优先级最低的任务
            Console.WriteLine(task);
        }
    }
}

输出：

Task B

Task C

Task A

2. 带重复优先级的队列

var priorityQueue = new PriorityQueue<string, int>();

priorityQueue.Enqueue("Task A", 1);
priorityQueue.Enqueue("Task B", 1);
priorityQueue.Enqueue("Task C", 2);

while (priorityQueue.Count > 0)
{
    Console.WriteLine(priorityQueue.Dequeue());
}

输出：

Task A

Task B

Task C

3. Peek 用法

Peek 方法用于查看队列中优先级最高的元素，而不移除它：

var priorityQueue = new PriorityQueue<string, int>();

priorityQueue.Enqueue("Task A", 3);
priorityQueue.Enqueue("Task B", 1);

Console.WriteLine(priorityQueue.Peek()); // 输出 "Task B"
Console.WriteLine(priorityQueue.Count); // 输出 2

4. 批量添加元素

var priorityQueue = new PriorityQueue<string, int>();

// 批量添加元素
priorityQueue.EnqueueRange(new[]
{
    ("Task A", 3),
    ("Task B", 1),
    ("Task C", 2)
});

while (priorityQueue.Count > 0)
{
    Console.WriteLine(priorityQueue.Dequeue());
}

输出：

Task B

Task C

Task A

5. 自定义优先级比较器

可以使用自定义比较器来定义优先级排序规则：

var priorityQueue = new PriorityQueue<string, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));

// 添加元素
priorityQueue.Enqueue("Task A", 3);
priorityQueue.Enqueue("Task B", 1);
priorityQueue.Enqueue("Task C", 2);

while (priorityQueue.Count > 0)
{
    Console.WriteLine(priorityQueue.Dequeue());
}

输出：

Task A

Task C

Task B

注意：在自定义比较器中，y.CompareTo(x) 将改变排序为从高到低（降序）。

PriorityQueue 方法说明

Enqueue(element, priority) 将元素添加到队列，并指定优先级。
Dequeue() 移除并返回优先级最高的元素（默认是最小优先级）。
Peek() 返回优先级最高的元素，但不从队列中移除。
EnqueueRange() 批量添加元素，提供 (element, priority) 的元组集合。
TryDequeue(out element, out priority) 尝试移除并返回优先级最高的元素和对应优先级。
Count 获取队列中的元素数量。

PriorityQueue 使用场景

任务调度：基于优先级处理任务（如操作系统调度）。

路径规划：例如 Dijkstra 算法中的优先级队列。

事件系统：处理基于优先级的事件。

资源分配：按优先级分配系统资源。

注意事项

优先级排序：默认情况下，PriorityQueue 会按升序排序（即优先级值越小，越优先）。可以通过自定义比较器调整排序规则。

线程安全性：PriorityQueue 本身是非线程安全的，需在多线程环境中使用适当的同步机制。

性能：插入和移除操作的时间复杂度为 O(log n)，适合处理大量数据的场景。

PriorityQueue<TElement, TPriority> 是处理优先级队列的强大工具，可以帮助开发者轻松实现高效的优先级排序和处理。