Làm việc với PriorityQueue của .NET 6

Với mỗi bản phát hành mới của .NET đều có những bổ sung thú vị cho thư viện lớp cơ sở và .NET 6 cũng không phải là ngoại lệ.

Những người yêu thích cấu trúc dữ liệu sẽ vui mừng khi thấy một kiểu mới là PriorityQueue được thêm vào BCL bên trong namespace System.Collections.Generic.

Bài viết này sẽ giúp bạn tìm hiểu PriorityQueue là gì, cách chúng ta thêm các phần tử và cách chúng ta có thể xếp hàng lại cho các phần tử bên trong chúng.

Hàng đợi là gì?

Hàng đợi (Queue) là cấu trúc dữ liệu cơ bản đầu tiên trong khoa học máy tính. Hàng đợi là lý tưởng để xử lý các tập dữ liệu phải theo dõi thứ tự chính xác (vào trước ra trước - FIFO).

Các phần tử được lấy ra (dequeue) sẽ bị xóa khỏi hàng đợi. Hãy xem một ví dụ đơn giản bằng cách sử dụng cấu trúc dữ liệu Queue của .NET.

var numbers = new Queue<string>();
numbers.Enqueue("one");
numbers.Enqueue("two");
numbers.Enqueue("three");
numbers.Enqueue("four");
numbers.Enqueue("five");

// A queue can be enumerated without disturbing its contents.
while(numbers.TryDequeue(out var number) )
{
    Console.WriteLine(number);
}

Console.WriteLine(numbers.Count);

Lệnh gọi TryDequeue sẽ xóa và trả về giá trị của phần tử ở phía trước của hàng đợi. Trong trường hợp của ví dụ này, chúng ta có thể mong đợi việc thực thi của chúng ta sẽ dẫn đến kết quả sau.

one
two
three
four
five
0

Bây giờ chúng ta đã hiểu cách hoạt động của Queue, vậy PriorityQueue khác với Queue như thế nào?

Hàng đợi ưu tiên là gì?

Giống như hàng đợi (Queue), hàng đợi ưu tiên (PriorityQueue) vẫn là cấu trúc vào trước ra trước (FIFO). Sự khác biệt là mức độ ưu tiên do người dùng chỉ định xác định phần tử nào là “đầu tiên” chứ không phải thứ tự mà chúng ta thêm các phần tử vào hàng đợi.

Trong trường hợp .NET 6, kiểu PriorityQueue xác định mức độ ưu tiên của các giá trị bằng cách sử dụng việc triển khai interface IComparer. Hãy cùng xem qua ví dụ mẫu ở bên dưới. Chúng ta sẽ thêm Siêu anh hùng vào một PriorityQueue kèm theo thông tin Greatness của họ.

PriorityQueue nhận hai đối số generic, đối số đầu tiên là giá trị của phần tử trong hàng đợi và đối số thứ hai là độ ưu tiên. Hàm khởi tạo cũng có thể nhận một đối tượng IComparer nhưng không bắt buộc vì hầu hết các kiểu nguyên thủy trong .NET đã có một triển khai so sánh mặc định.

using System;
using System.Collections.Generic;
using static Greatness;

PriorityQueue<string, Greatness> superheroes = new(new GreatnessComparer());

superheroes.Enqueue("Hawkeye", Meh);
superheroes.Enqueue("Captain America", GOAT);
superheroes.Enqueue("Mantis", Ok);
superheroes.Enqueue("Scarlet Witch", Good);
superheroes.Enqueue("Black Widow", Meh);
superheroes.Enqueue("Spider-Man", Great);
superheroes.Enqueue("Dr. Strange", Good);
superheroes.Enqueue("Thor", Great);
superheroes.Enqueue("Shuri", Great);
superheroes.Enqueue("Black Panther", Great);
superheroes.Enqueue("Iron Man", Ok);
superheroes.Enqueue("Hulk", Good);

Console.WriteLine("Oh No! Hydra is attacking.");
Console.WriteLine("Avengers... Assemble!");

while (superheroes.TryDequeue(out var hero, out var greatness))
{
    Console.WriteLine($"{hero} ({greatness}) has joined the fight...");
}

public class GreatnessComparer: IComparer<Greatness>
{
    // highest to lowest
    public int Compare(Greatness x, Greatness y) => y - x;
}

public enum Greatness
{
    Meh,
    Ok,
    Good,
    Great,
    GOAT
}

Trong ví dụ này, chúng ta sẽ thấy các siêu anh hùng của chúng ta tham gia cuộc chiến theo thứ tự Greatness từ cao nhất đến thấp nhất. PriorityQueue sẽ xác định thứ tự ưu tiên của các siêu anh hùng bằng cách sử dụng đối tượng của class GreatnessComparer được triển khai từ interface IComparer. Khi thực thi chương trình, chúng ta sẽ thấy kết quả sau.

Oh No! Hydra is attacking.
Avengers... Assemble!
Captain America (GOAT) has joined the fight...
Spider-Man (Great) has joined the fight...
Thor (Great) has joined the fight...
Shuri (Great) has joined the fight...
Black Panther (Great) has joined the fight...
Hulk (Good) has joined the fight...
Dr. Strange (Good) has joined the fight...
Scarlet Witch (Good) has joined the fight...
Mantis (Ok) has joined the fight...
Iron Man (Ok) has joined the fight...
Hawkeye (Meh) has joined the fight...
Black Widow (Meh) has joined the fight...

Chúng ta có thể thấy rằng những anh hùng mạnh nhất của trái đất đã bắt đầu cuộc chiến, tạo cơ hội cho Hawkeye và Black Widow sống sót.

Phần kết luận

Cấu trúc dữ liệu PriorityQueue là một bổ sung tuyệt vời cho namespace System.Collections.Generic, và tôi rất vui khi xem cách nó được sử dụng trong các ứng dụng của bạn. Nó khác với Queue vì định nghĩa của phần tử đầu tiên (first) dựa trên việc triển khai interface IComparer, có thể xác định thứ tự trên bất kỳ tập hợp nào.

Tôi hy vọng bạn thấy bài viết này hữu ích, và vui lòng để lại bình luận và chia sẻ bài viết này.

Nếu Comdy hữu ích và giúp bạn tiết kiệm thời gian làm việc

Bạn có thể vui lòng đưa Comdy vào whitelist của trình chặn quảng cáo ❤️ để hỗ trợ chúng tôi trong việc trả tiền cho dịch vụ lưu trữ web để duy trì hoạt động của trang web.

Lập Trình C#.NET 6
Bài Viết Liên Quan:
Tạo tập tin Zip với .NET 5
Trung Nguyen 11/11/2021
Tạo tập tin Zip với .NET 5

Trong bài viết này, chúng ta sẽ tìm hiểu lớp tiện ích ZipFile trong C#, cách nén tập tin và thư mục, cùng với giải nén tập tin zip.

Đọc và ghi file Excel trong C#
Trung Nguyen 29/10/2021
Đọc và ghi file Excel trong C#

Bài viết này sẽ giới thiệu cách đơn giản nhất mà tôi đã tìm thấy để đọc và ghi file Excel bằng C# sử dụng ExcelMapper.

Hướng dẫn nhanh và ví dụ về pattern matching trong C#
Trung Nguyen 23/10/2021
Hướng dẫn nhanh và ví dụ về pattern matching trong C#

Bài viết này sẽ trình bày một số ví dụ về pattern matching hữu ích và bạn có thể xem xét sử dụng trong các dự án hiện tại hoặc tương lai của bạn.

Sử dụng chuỗi kết nối Redis-CLI trong StackExchange.Redis
Trung Nguyen 18/10/2021
Sử dụng chuỗi kết nối Redis-CLI trong StackExchange.Redis

Bài viết này sẽ hướng dẫn chúng ta cách viết một phương thức mở rộng để phân tích chuỗi kết nối redis-cli có thể sử dụng với thư viện StackExchange.Redis.