Giới thiệu priority_queue:
Priority queue là một loại container adaptor, được thiết kế đặc biệt để phần tử ở đỉnh luôn luôn là phần tử có độ ưu tiên lớn nhất so với các phần tử khác.
Nó giống như một heap, mà ở đây là heap max, tức là phần tử có độ ưu tiên lớn nhất có thể được lấy ra và các phần tử khác được chèn vào bất kì.
Khác với queue, priority_queue không có khái nhiệm front, back mà chỉ có khái nhiệm top tương tự như stack.
Độ ưu tiên có thể sử dụng các phép toán trong thư viện functional hoặc lập trình viên có thể tự định nghĩa.
Phép toán so sánh mặc định khi sử dụng priority queue là phép toán less [Xem thêm ở thư viện functional].
Một số phép toán so sánh của thư viện functional:
| equal_to | Bằng [==] |
| not_equal_to | Không bằng [!=] |
| greater | Lớn hơn [>] |
| less | Nhỏ hơn [ |
| greater_equal | Lớn hơn hoặc bằng [>=] |
| less_equal | Nhỏ hơn hoặc bằng [ |
Để sử dụng priority queue một cách hiệu quả, các bạn nên học cách viết hàm so sánh để sử dụng cho linh hoạt cho từng bài toán.
Khai báo priority_queue:
Trong C++ không có thư viện priority_queue, do đó, để sử dụng priority_queue, ta cần khai báo thư viên queue:
#include
Khai báo với phép toán mặc định là less:
priority_queue myPriorityQueue;
Ta có thể tưởng tượng priority_queue tương tự như stack, do đó, phần tử có độ ưu tiên lớn nhất sẽ nằm về phía bên phải [Như hình ảnh ở phần giới thiệu priority_queue]. Do đó, khi sử dụng phép toán less, phần tử độ ưu tiên cao nhất là phần tử có giá trị lớn nhất.
Khai báo với phép toán khác:
Ví dụ: sử dụng phép toán greater của thư viện functional
priority_queue myPriorityQueue ;
Khi sử dụng phép toán greater, phần tử độ ưu tiên cao nhất là phần tử có giá trị nhỏ nhất.
Khai báo sử dụng class so sánh tự định nghĩa:
Ta sử dụng một struct kết hợp với nạp chồng toán tử dấu ngoặc đơn như ví dụ bên dưới:
structcmp{ cmp{ booloperator[][inta,intb]{returna operator[] [int a,int b] {return a Chủ Đề |