Stack, Queue và Priority Queue trong Java (Phần 3)

Stack, Queue và Priority Queue trong Java

Phần 3: Priority Queue

1.     Định nghĩa

Priority Queue là gì?

Priority Queue là một danh sách dạng biến thể của queue với thứ tự sắp xếp dựa trên mức độ ưu tiên của phần tử. Tức danh sách này có cấu trúc đưa vào và đưa ra giống queue, chỉ có một điểm khác là sau khi đưa vào thì nó sẽ đẩy phần tử mới vào vị trí phù hợp theo thứ tự giảm dần từ rear – có giá trị cao nhất, đến top – có giá trị thấp nhất.
Nói một chút về giá trị ưu tiên (priority). Về mặt tổng quan, đó là một cách để sắp xếp công việc nào sẽ được thực hiện trước, công việc nào sẽ được thực hiện sau. Về mặt cụ thể, đây là chỉ số giúp cho ta biết được phần tử nào sẽ được đưa ra ngoài trước, phần tử nào sẽ được đưa ra ngoài sau. Theo quy tắc trong đây, giá trị nào được xem như là nhỏ nhất thì sẽ được thực hiện trước. (Lưu ý: Việc định giá trị của 1 phần tử lớn hay nhỏ không theo 1 công thức cụ thể, mà phụ thuộc vào từng bài toán khác nhau).

     Note: Mức độ ưu tiên trong Linux đối với các chương trình là chỉ số NI, chỉ số này càng cao thì độ ưu tiên càng tăng. Trong các trình soạn thảo hoặc trình chiếu như PowerPoint cũng có thể sử dụng mức độ ưu tiên để xác định các ảnh chồng chất lên nhau, ảnh nào có độ ưu tiên cao hơn thì sẽ được chồng lên trên cùng (việc quy định số cao hay thấp sẽ ưu tiên trước phụ thuộc vào nhà phát triển).

Một bức hình đơn giản cho các bạn thấy được cách thức vận hành của priority queue như thế nào. (Nguồn: https://www.callicoder.com/java-priority-queue/)

Khi bạn muốn lấy một phần tử ra ngoài, thì phần tử tại vị trí front sẽ lấy ra trước. Khi bạn thêm phần tử, nó sẽ thêm tại rear và chọn vị trí phù hợp để đứng

2.     Sử dụng Priority Queue trong Java

Giống với Stack và khác với Queue, Priority Queue đều khai báo và khởi tạo thông qua cùng một lớp là PriorityQueue. Cú pháp chắc các bạn có thể đoán được rồi

PriorityQueue<Object> pQueue = new PriorityQueue<Object>();

Vì Priority Queue được sắp xếp thông qua độ ưu tiên, mà độ ưu tiên do chúng ta quy định, nên sẽ có thêm một công đoạn quy định độ ưu tiên cho phần tử. Đúng vậy, đó là xây dựng một Comparator. Bạn hình dung comparator với hai phần tử obj1 và obj2, obj1 đại diện cho phần tử chúng ta vừa chèn vào, và obj2 đại diện cho các phần tử đã có trên danh sách. Và ta có một quy định như sau

obj1 > obj2 <=> +

obj1 < obj2 <=> -

obj1 = obj2 <=> 0

Khi đó, class PriorityQueue của chúng ta sẽ ngầm hiểu ý nghĩa của các con số dương là gì, âm là gì, và 0 là gì thông qua quy tắc trên. Với xu hướng đẩy con số nhỏ nhất lên trên đầu, nó sẽ đẩy obj1 đi lên khi gặp số -, và sẽ dừng lại khi obj1 > obj2 hoặc obj1 = obj2. Nên nhớ, đây là quy tắc, tức chúng ta thực ra đang truyền thông tin thực sự rằng obj1 > obj2, hay obj1 < obj2, hay obj1 = obj2. Giả sử như sau

Giá trị ưu tiên đầu tiên sẽ là số 5

Vì sao? Vì chúng ta quy định obj1 sẽ nhỏ hơn obj2 (-1) khi value1 < value2, tức là phần tử có giá trị nhỏ hơn thì độ ưu tiên sẽ nhỏ hơn. Còn nếu chúng ta lật ngược lại trạng thái

Kết quả trả về là 10, với 10 là phần tử có độ ưu tiên nhỏ nhất

Vì sao? (Chú ý dòng phát sáng) Chúng ta quy định giá trị phần tử đầu tiên nếu lớn hơn phần tử thứ 2, thì obj1 sẽ có độ ưu tiên bé hơn obj2 (-1).

Chú ý: Mức độ ưu tiên sẽ không phụ thuộc vào value1 hoặc value2 trên, mà phụ thuộc vào cách chúng ta quy định dựa vào một điều kiện nào đó. Ở đây là với điều kiện số càng lớn thì độ ưu tiên càng bé

Một trò vui nho nhỏ áp dụng kiến thức chúng ta vừa học xem nào. Nếu chúng ta quy định obj1 luôn nhỏ hơn obj2 thì sao nào? Hãy xem nhé

Kết quả: 6 10 5

Ôi dào, thế phải chăng một obj mới khi đưa vào luôn ưu tiên lên đầu tiên sao, tức là mình quy định mọi số mới khi đưa vào luôn có độ ưu tiên nhỏ nhất, cho nên số nào vào trước thì sẽ ra trước. First In First Out, hừm nghe có vẻ như một Stack nhỉ, chỉ là cấu trúc và cách hoạt động của nó không giống Stack, nhưng chức năng của nó thì y chang.

Nếu đảo ngược lại obj1 luôn lớn hơn obj2 thì sao, câu trả lời rõ rồi nhỉ. Nó sẽ là 1 Queue thuần túy, với cấu trúc và cách vào ra giống y hệt Queue. Haha khi hiểu được cách thức hoạt động của comparator thì chiều xử lý của Priority Queue này các bạn có thể nắm dễ như trở bàn tay.

Với các hàm lấy vào và lấy ra, các bạn có thể thấy rõ đó là hàm add() và hàm remove(), vì chức năng giống với queue nên mình không cần phải giải thích lại nhỉ. Còn một số hàm khác các bạn có thể tham khảo thêm, trên mạng có khá nhiều rồi. Mình chỉ nói chi tiết những cái mà trên mạng ít hoặc không nói đến thôi.
 

Nội dung bài viết thuộc về Lê Công Diễn.

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn