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 PriorityQueuelà 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 Queuecủ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 TryDequeuesẽ 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áchhoạt động của Queue, vậy PriorityQueue khác với Queuenhư 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ọ.

PriorityQueuenhậ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ự Greatnesstừ cao nhất đến thấp nhất. PriorityQueuesẽ 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 Queuevì đị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.