当前位置： 首页 > ai >正文

C#进阶学习（十七）PriorityQueue＜TElement, TPriority＞优先级队列的介绍

ai 2025/5/2 19:02:06

1. PriorityQueue是什么？作用是什么？

        定义：PriorityQueue<TElement, TPriority> 是 C# (.NET 6+ 引入) 中的泛型优先级队列数据结构。

        那么是什么是优先级队列呢？优先级队列是一种抽象数据结构，其核心特性是元素按照优先级顺序进行管理，而非传统队列的先进先出（FIFO）规则。在优先级队列中，每次被取出处理的元素是当前队列中优先级最高的（或最低的，取决于具体实现），而非最早进入队列的元素。这种特性使其在需要动态调整处理顺序的场景中具有独特优势。

        作用：按优先级管理元素，优先级高（值小）的元素先出队。常用于需要按特定顺序处理任务的场景，如：

任务调度（高优先级任务优先执行）。

算法实现（如 Dijkstra 最短路径算法、Huffman 编码）。

事件驱动系统（按时间戳处理事件）。

2. 底层实现与复杂度

        底层结构：基于 二叉堆（最小堆） 实现，确保堆顶元素始终是优先级最高的（即优先级值最小）。

  • 时间复杂度：

    入队 (Enqueue)：O(log n)。

    出队 (Dequeue)：O(log n)。

    查看堆顶 (Peek)：O(1)。

  • 空间复杂度：O(n)（动态数组存储堆节点）。

3.优先级的次序

        在 C# 的 PriorityQueue<TElement, TPriority> 中，优先级规则完全由 TPriority 类型的比较逻辑决定。默认的次序如下：

（1） 数值类型（如 int、double 等）

        默认规则：优先级值 越小 的优先级越高（即最小堆）。

        示例：

var queue = new PriorityQueue<string, int>();
queue.Enqueue("Task 1", 3);
queue.Enqueue("Task 2", 1); // 优先级更高
queue.Enqueue("Task 3", 2);
// 出队顺序：Task 2 → Task 3 → Task 1

（2） 字符串类型（string） 

        默认规则：按 字典序（区分大小写）升序排序。

                比较规则："A" < "B" < "a" < "b"（基于 Unicode 码点）。

        示例：

var queue = new PriorityQueue<string, string>();
queue.Enqueue("Apple", "Zebra"); // 优先级低
queue.Enqueue("Banana", "Apple"); // 优先级高
// 出队顺序：Banana（Apple） → Apple（Zebra）

        小结，默认里面是按照升序进行组成的，每次默认弹出的是优先级最高的，想自定义出队列规则，需要自定义比较器 。若要覆盖默认规则（如让数值越大优先级越高），需实现 IComparer<TPriority> 接口，并在构造函数中传入比较器。例如：

示例 1：数值降序优先级（最大堆）
using System.Collections.Generic;// 自定义比较器：数值越大优先级越高
public class MaxPriorityComparer : IComparer<int>
{public int Compare(int x, int y) => y.CompareTo(x); // 反转默认顺序
}public class Program
{public static void Main(){// 使用自定义比较器var queue = new PriorityQueue<string, int>(new MaxPriorityComparer());queue.Enqueue("Task 1", 3); // 优先级高（数值大）queue.Enqueue("Task 2", 1); // 优先级低queue.Enqueue("Task 3", 2);// 出队顺序：Task 1 → Task 3 → Task 2}
}
示例 2：字符串按长度排序
public class StringLengthComparer : IComparer<string>
{public int Compare(string x, string y) => x.Length.CompareTo(y.Length);
}public class Program
{public static void Main(){var queue = new PriorityQueue<string, string>(new StringLengthComparer());queue.Enqueue("Apple", "Zebra");    // 长度 5queue.Enqueue("Banana", "Ant");     // 长度 3 → 优先级更高queue.Enqueue("Cherry", "Elephant");// 长度 8// 出队顺序：Banana → Apple → Cherry}
}

小结：

场景规则实现方式
默认优先级（数值升序）值越小优先级越高无需额外代码，直接使用默认队列
数值降序（最大堆）值越大优先级越高自定义 IComparer<int>
字符串按长度排序长度越短优先级越高自定义 IComparer<string>
不区分大小写的字符串排序按字母顺序忽略大小写自定义 IComparer<string>

4. 主要使用方式与代码示例

示例 1：基本使用（默认升序优先级）

using System;
using System.Collections.Generic;var priorityQueue = new PriorityQueue<string, int>();// 入队：元素 + 优先级（优先级值越小，优先级越高）
priorityQueue.Enqueue(element: "Task 1", priority: 3); // 低优先级
priorityQueue.Enqueue("Task 2", 1); // 高优先级
priorityQueue.Enqueue("Task 3", 2);// 出队：按优先级升序（值小的先出）
while (priorityQueue.TryDequeue(out string task, out int priority))
{Console.WriteLine($"处理任务: {task}, 优先级: {priority}");
}
// 输出顺序：
// 处理任务: Task 2, 优先级: 1
// 处理任务: Task 3, 优先级: 2
// 处理任务: Task 1, 优先级: 3
示例 2：自定义降序优先级比较器

关于比较器的知识可以看这里：C#中的比较器

// 自定义比较器：优先级值越大，优先级越高
public class MaxPriorityComparer : IComparer<int>
{public int Compare(int x, int y) => y.CompareTo(x); // 降序
}public class Program
{public static void Main(){// 使用自定义比较器初始化队列var queue = new PriorityQueue<string, int>(new MaxPriorityComparer());queue.Enqueue("Task A", 5);queue.Enqueue("Task B", 10); // 优先级更高（值更大，但比较器反转逻辑）while (queue.TryDequeue(out var task, out var priority)){Console.WriteLine(task); // 输出顺序：Task B → Task A}}
}
示例 3：处理队列为空的情况
var queue = new PriorityQueue<char, int>();
queue.Enqueue('A', 1);// 安全出队（避免异常）
if (queue.TryDequeue(out char element, out int priority))
{Console.WriteLine($"出队元素: {element}");
}if (!queue.TryDequeue(out element, out priority))
{Console.WriteLine("队列为空！");
}

5. 主要 API 和属性汇总

属性
属性名类型说明
Countint队列中当前元素的数量。
方法
方法名参数返回值/行为
Enqueue(TElement element, TPriority priority)element: 元素；priority: 优先级将元素按优先级插入队列。
Dequeue()无移除并返回优先级最高的元素。若队列为空，抛出 InvalidOperationException。
TryDequeue(out TElement element, out TPriority priority)element: 出队元素；priority: 优先级安全出队，返回是否成功。若队列为空，返回 false。
Peek()无返回优先级最高的元素但不移除。若队列为空，抛出异常。
TryPeek(out TElement element, out TPriority priority)element: 堆顶元素；priority: 优先级安全查看堆顶元素，返回是否成功。若队列为空，返回 false。
Clear()无清空队列中的所有元素。
构造函数
构造函数说明
PriorityQueue()使用默认优先级比较器（升序）。
PriorityQueue(IComparer<TPriority>? comparer)指定自定义优先级比较器。
PriorityQueue(IEnumerable<(TElement Element, TPriority Priority)> items)从现有元素集合初始化队列。

        其中两个重要方法的解释：

构造函数 PriorityQueue(IEnumerable<(TElement, TPriority)> items)

        作用：通过一个包含元素及其优先级的元组集合 批量初始化优先级队列，直接构建堆结构，避免多次调用 Enqueue 的开销。说白了，其实就是初始化，你直接塞一个这样的组合进去。

        特点:

批量添加优化:

时间复杂度：O(n)O(n)（直接构建堆，比逐个调用 Enqueue 的 O(nlog⁡n)O(nlogn) 更高效）。空间复杂度：O(n)O(n)（存储所有元素）。

自动堆化（Heapify）:
内部会将传入的集合直接转换为堆结构，无需手动调整顺序。

支持自定义比较器:
可结合其他构造函数指定优先级比较规则。就是，你在初始化之后，直接往后面，塞一个比较器，他是支持这个重载的。

示例：

using System;
using System.Collections.Generic;var items = new List<(string Element, int Priority)>
{("Task 1", 3),("Task 2", 1), // 高优先级("Task 3", 2)
};// 使用集合初始化队列
var queue = new PriorityQueue<string, int>(items);// 出队顺序：Task 2 → Task 3 → Task 1
while (queue.TryDequeue(out var task, out var priority))
{Console.WriteLine($"{task} (优先级: {priority})");
}

方法 TryDequeue(out TElement element, out TPriority priority)

        作用：安全地取出并删除优先级最高的元素，避免队列为空时抛出异常。适合不确定队列状态时的安全操作。

        特点：

返回值

true：成功取出元素，element 和 priority 参数被正确赋值。

false：队列为空，element 和 priority 赋为 default(TElement) 和 default(TPriority)。

非破坏性检查：

        与 Dequeue() 不同，此方法不会在队列为空时抛出异常，而是通过返回值明确操作结果。

例如：

var queue = new PriorityQueue<char, int>();
queue.Enqueue('A', 3);
queue.Enqueue('B', 1);// 安全出队
if (queue.TryDequeue(out char element, out int priority))
{Console.WriteLine($"出队元素: {element} (优先级: {priority})"); // B (优先级: 1)
}// 队列未空时继续操作
if (queue.TryDequeue(out element, out priority))
{Console.WriteLine($"出队元素: {element} (优先级: {priority})"); // A (优先级: 3)
}// 队列已空时处理
if (!queue.TryDequeue(out element, out priority))
{Console.WriteLine("队列为空！"); // 输出此句Console.WriteLine($"element 的默认值: {element}"); // 输出 '\0'（char 的默认值）Console.WriteLine($"priority 的默认值: {priority}"); // 输出 0（int 的默认值）
}
与 Dequeue() 的对比
方法行为适用场景
Dequeue()直接取出元素，队列为空时抛出异常确定队列非空时简化代码
TryDequeue(...)安全取出元素，通过返回值处理空队列情况

不确定队列状态时避免异常

6.注意事项 

        （1）PriorityQueue<TElement, TPriority> 是 .NET 6 及以上版本中引入的泛型数据结构，仅在 .NET 6、.NET 7、.NET 8 及后续版本中可用。若项目目标框架为旧版本（如 .NET 5、.NET Core 3.1 或更早），则无法直接使用此类型。需通过升级项目框架或寻找替代方案（如第三方库）解决兼容性问题。

        （2）PriorityQueue<TElement, TPriority> 默认允许插入重复元素（即使元素值和优先级均相同）。若需确保队列中元素的唯一性，需自行维护逻辑，例如通过 HashSet<TElement> 跟踪已存在的元素，仅在元素未添加时调用 Enqueue。

         （3）默认值陷阱：当队列为空时，TryDequeue 方法会将输出参数设为 TElement 和 TPriority 的默认值（如 int 为 0，引用类型为 null）。需通过返回值判断操作是否成功，避免误用默认值导致逻辑错误。异常风险：直接调用 Dequeue() 或 Peek() 方法时，若队列为空会抛出 InvalidOperationException。建议优先使用 TryDequeue 和 TryPeek 方法，以规避异常风险。

http://www.xdnf.cn/news/2909.html

相关文章：

  • 阿里云服务器 篇十二：加入 Project Honey Pot 和使用 http:BL
  • 万象生鲜配送系统代码2025年4月29日更新日志
  • Java练习3
  • c语言的常用的预处理指令和条件编译
  • __proto__与prototype
  • 误在非开发分支上开发解决方案
  • LabVIEW实验室项目中使用类模块与仿真
  • Linux 怎么安装 Oracle Java 8
  • 通过logrotate和cronolog对日志进行切割
  • 什么是DNS缓存？怎么清理DNS缓存？
  • 网络安全攻防演练实训室建设方案
  • 9.idea中创建springboot项目
  • Next框架学习篇 ✅
  • Nginx部署与源码编译构建LAMP
  • Java基础 4.29
  • OpenJDK 1.8中-Xloggc参数下GC日志覆盖与追加模式深度解析
  • 软文发稿：媒体发稿的关键策略及实战价值
  • Android Studio中OpenCV应用详解：图像处理、颜色对比与OCR识别
  • 水污染检测数据集VOC+YOLO格式2487张4类别
  • mangodb的数据库与集合命令，文档命令
  • 字节跳动社招面经 —— BSP驱动工程师（4）
  • 【计算机网络】DHCP——动态配置ip地址
  • 仿真干货｜云端CAE实战——OpenRadioss物品碰撞模拟分析
  • day006
  • FPGA 39 ，FPGA 网络通信协议栈进阶，RGMII、ARP 与 UDP 协议与模块设计（ RGMII、ARP、UDP原理与模块设计 ）
  • 基于STM32的中点圆算法，画空心圆的函数
  • 【MongoDB篇】MongoDB的数据库操作！
  • 通义千问最新一代大语言模型Qwen3发布了
  • 前端漏洞不扫描理由
  • 各服务日志: Grok正则解析