Priority queue là gì

     
Mở đầu Mở đầu Hàng đợi ưu tiên Hàng đợi ưu tiên Heap ra mắt về Heap, max heap Min Heap sắp xếp heap sort Bảng băm - Hash table Bảng băm - Hash table giải quyết xung đột - Separate chaining

Trong bài này chúng ta sẽ cùng nhau tìm hiểu về hàng đợi ưu tiên.

Bạn đang xem: Priority queue là gì

Nếu bạn đã đọc qua loạt bài học về cấu trúc dữ liệu vun đống - heap, thì bạn sẽ biết hàng đợi ưu tiên là một ứng dụng của heap.

Tuy nhiên bạn có thể thực hiện hàng đợi ưu tiên mà ko cần dùng heap. Tuy nhiên dùng heap để xây dựng hàng đợi ưu tiên là cách hiệu quả, tối ưu và tuyệt được dùng nhất.

Trong một số ngôn ngữ như C++ thì hàng đợi ưu tiên đã được đến vào trong bộ thư viện chuẩn và ta chỉ việc gọi ra để dùng,các bạn có thể tham khảo ở đây. Tuy nhiên trong rất nhiều các trường hợp khác ta phải tự tay xây dựng hàng đợi ưu tiên và cải tiến nó để giải quyết được các bài toán phức tạp hơn.

Định nghĩa hàng đợi ưu tiên

Hàng đợi ưu tiên cũng có những tính chất giống như hàng đợi đó là chèn phần tử vào phía cuối và lấy ra từ phía đầu. Dẫu vậy có điểm khác đó là thứ tự các phần tử trong hàng đợi ưu tiên phụ thuộc vào dộ ưu tiên của phần tử đó.còn hàng đợi bình thường thì tuân thủ theo đúng tính chất FIFO (vào trước ra trước).

Phần tử với độ ưu tiên cao nhất sẽ được xếp lên đầu hàng đợi và phần tử với độ ưu tiên thấp nhất sẽ được chuyển xuống cuối.

Do vạy, khi bạn chèn một phần tử vào cuối hàng đợi ưu tiên, no có thể được chuyển lên đầu tiên nếu độ ưu tiên của nó là cao nhất.

Ví dụ về hàng đợi ưu tiên

Giả sử ta có một mảng với 5 phần tử: 4, 8, 1, 7, 3 và bạn phải chèn các phần tử này vào một hàng đợi ưu tiên theo giá trị lớn nhất.

Bước 1: Ban đầu hàng đợi rỗng, vày vậy 4 được chèn vào.

Bước 2: Chèn 8 vào hàng đợi, bởi 8 lớn rộng 4 lên 8 được đẩy lên đầu hàng đợi.

Bước 3: chèn 1 vào hàng đợi, 1 nhỏ hơn 4 và 8 đề nghị 1 giữ nguyên vị trí ở cuối hàng đợi.

Bước 4: Chèn 7 vào hàng đợi, 7 lớn rộng 1 và 4, nhỏ rộng 8 đề xuất 7 được đẩy lên vị trí nằm giữa 4 và 8.

Bước 5: Chèn 3 vào hàng đợi, 3 lớn rộng 1 và nhỏ rộng 4 lên 3 được đẩy lên vị trí nằm giữa 1 và 4.

Tất cả các bước được tế bào tả dưới hình sau:

*

Hình 1: mô tả hoạt động của hàng đợi ưu tiên

Có nhiều cách để xây dựng hàng đợi ưu tiên.

Cách tiếp cận solo giản

Giả sử ta có N phần tử và phải chèn chúng vào hàng đợi ưu tiên. Chúng ta có thể sử dụng danh sách liên kết để thực hiện chèn các phần tử với độ phức tạp O(N) (trong trường hợp ta chèn phần tử vào cuối danh sách liên kết)và có thể sắp xếp lại chúng để duy trì các đặc tính của hàng đợi ưu tiên với độ phức tạp O(NlogN).

Xem thêm: Cách Thay Đổi Tên Gmail Trên Điện Thoại, Thay Đổi Địa Chỉ Email Cho Tài Khoản Của Bạn

Cách tiếp cận tối ưu

Sử dụng heap để xây dựng hàng đợi ưu tiên với độ phức tạp là O(logN) mang đến việc chèn và xóa phần tử khỏi hàng đợi.

Dựa vào cấu trúc heap, hàng đợi ưu tiên cũng chia nhỏ ra làm hai loại là hàng đợi ưu tiên theo giá trị lớn nhất (max -priority queue) và hàng đợi ưu tiên theo giá trị nhỏ nhất (min - priority queue).

Trong phạm vi bài học này chúng ta sẽ đi sâu vào tìm hiểu hàng đợi ưu tiên theo giá trị lớn nhất. Cách xây dựng hàng đợi ưu tiên theo giá trị nhỏ nhất cũng tương tự như vậy.

Hàng đợi ưu tiên theo giá trị lớn nhất có thể thực hiện các thao tác sau:

Trả về phần tử lớn nhất trong hàng đợi ưu tiên.Xóa phần tử có giá trị lớn nhất ra khỏi hàng đợi ưu tiên và trả về giá trị của nó.Chèn phần tử vào hàng đợi ưu tiên.Cài đặt hàng đợi ưu tiên - priority queue

Ta cùng xét cách viết các hàm thực hiện các thao tác trong hàng đợi ưu tiên.

Giả sử ta có A là mảng để lưu các phần tử của hàng đợi ưu tiên.

N là số phần tử hiện có trong hàng đợi.

Hàm chèn phần tử vào hàng đợi ưu tiên:

Khi chèn phần tử vào hàng đợi, nó có thể vi phạm các quy tắc của max heap, nếu vậy ta phải thực hiện đổi chỗ giá trị node phụ vương và của node đó mang đến tới lúc ta có được giá trị của node thân phụ là lớn hơn.

void insert_element(int A< >, int val){ N = N + 1; /* Tăng kích thước của hàng đợi lên 1 khi ta chèn thêm phần tử vào */ int i = N; /* N là biến toàn cục, không nên thay đổi giá trị của nó, ta sử dụng biến tạm i ở đây, để có thể tùy ý xử lý */ A< i > = val; /* Trước tiên phần tử được chèn vào vị trí cuối cùng của hàng đợi */ while( i > 1 & A< i/2 > Độ phức tạp về thời gian: O(logN)

Hàm trả về giá trị lớn nhất trong hàng đợi:

int max_element(int A< >) return A<1>; /* A<1> là node gốc vào max heap và node gốc trong max heap là node có giá trị lớn nhất */Độ phức tạp thời gian: O(1)

Hàm xóa phần tử lớn nhất ra khỏi hàng đợi ưu tiên và trả về giá trị của nó:

int pop_max_element (int A< >){ if(N == 0) { coutĐộ tinh vi thời gian: O(logN).

Ví dụ về các thao tác với hàng đợi ưu tiên

Gỉa sử ban đầu ta tất cả 5 phần tử trong hàng đợi ưu tiên như sau: 8,7,4,3,1

Ta xét chuỗi các thao tác làm việc sau:

Chèn phần tử mới vào hàng đợi ưu tiên

insert_element(A, 6). Khi chèn 6 vào hàng hóng trên, các quy tắc của hàng chờ ưu tiên bị phạm luật (vi phạm quy tắc của max heap). Vì vậy ta phải triển khai đổi vị trí với node chacủa nó, node có giá trị 4. Sau khoản thời gian đổi chỗ, những quy tắc của max heap được duy trì. Cùng xem hình biểu lộ dưới đây.

*

Hình 2: Chèn bộ phận vào hàng ngóng ưu tiên

Xóa bộ phận lớn duy nhất khỏi hàng đợi và trả về giá trị của nó

pop_max_element() đang lấy bộ phận có giá chỉ trị lớn nhất ra ngoài hàng đợi (node cội của max heap).

Như nghỉ ngơi hình dưới đây bộ phận có cực hiếm 8 sẽ tiến hành lấy ra, và thành phần cuối thuộc trong mặt hàng đợi có mức giá trị 4 sẽ tiến hành chuyển lên núm chỗ của thành phần vừa được đem ra. Bây giờ các quy tác của max heap bị phá vỡ đề nghị ta cần thực hiện hàm max_heap() để gia hạn lại các quy tắc này.

*

Hình 3: Xóa phần tử lớn tuyệt nhất khỏi hàng chờ ưu tiên theo giá trị to nhất

Mã nguồn rất đầy đủ của chương trình cài đặt hàng đợi ưu tiên

#includeusing namespace std;int N;void insert_element(int A< >, int val) N = N + 1; /* Tăng kích thước của hàng đợi lên 1 lúc ta chèn thêm phần tử vào */ int i = N; /* N là biến toàn cục, tránh việc thay đổi giá trị của nó, ta sử dụng biến tạm i ở đây, để có thể tùy ý xử lý */ A< i > = val; /* Trước tiên phần tử được chèn vào vị trí cuối cùng của hàng đợi */ while( i > 1 and A< i/2 > A ) /* N là số thành phần trong mảng, biến toàn cục */ largest = left; else largest = i; if(right A ) largest = right; if(largest != i ) swap (A , A); max_heap (A, largest); int max_element(int A< >) return A<1>; /* A<1> là node gốc trong max heap và node gốc trong max heap là node có giá trị lớn nhất */int pop_max_element (int A< >){ if(N == 0) { cout hiệu quả chương trình sau thời điểm chạy và kiểm soát tại https://www.onlinegdb.com.

*

Source code trên gitlab: https://gitlab.com/thevngeek/basic-data-structure/blob/master/hangdoiuutien.cpp

Ta rất có thể thấy với cách tiến hành như trên các bộ phận của hàng đợi ưu tiên tuy không luôn luôn sắp xếp theo đúng lắp thêm tự to trước, nhỏ xíu sau. Nhưng các lần lấy thành phần ra ngoài hàng đợi ta luôn luôn được bảo vệ rằng thành phần đó là bự nhất, bởi thế quy tắc thành phần có độ ưu tiên cao hơn sẽ được ra khỏi hàng đợi trước (được giao hàng trước) vẫn được duy trì đúng. Và ưu điểm của cách làm này đến ta lợi về vận tốc chạy chương trình.

Xem thêm: Sai Lầm Cần Tránh Khi Tắm Cho Trẻ Em Tắm Nhiều Có Tốt Không ?

Như vậy ta rất có thể ứng dụng hàng chờ ưu tiên để lập định kỳ công việc. Lúc ta có một hàng đợi với N công việc, mỗi các bước đều tất cả độ ưu tiên của riêng rẽ nó. Nếu công việc có độ ưu tiên cao nhất sẽ được xong xuôi trước và xóa sổ khỏi hàng đợi, ta hoàn toàn có thể dùng hàm pop_max_element() để thực hiện việc này. Và nếu trên mỗi thời khắc ta buộc phải thêm một quá trình mới vào hàng đợi, ta có thể dùng hàm insert_element() để thêm bộ phận với độ tinh vi về thời hạn là O(logN) và bảo trì các luật lệ của max heap (node cha luôn luôn có giá chỉ trị to hơn các node con).

Tham khảo

1.https://vi.wikipedia.org/wiki/%C4%90%E1%BB%91ng_nh%E1%BB%8B_ph%C3%A2n

2.https://www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/tutorial/