Hàng đợi ưu tiên

Trong C++, chúng ta cũng có cấu trúc dữ liệu gọi là hàng đợi ưu tiên (priority queue). Hàng đợi ưu tiên cung cấp một chức năng đặc biệt mà hàng đợi thông thường không có: mỗi phần tử được gán một giá trị ưu tiên và các phần tử được xử lý dựa trên mức độ ưu tiên của chúng.

Hàng đợi ưu tiên cơ bản được thiết kế sao cho phần tử đầu tiên là phần tử lớn nhất, còn các phần tử còn lại được sắp xếp theo thứ tự giảm dần.

priority_queue<dataType> queueName

Trước tiên, chúng ta cần thêm tệp tiêu đề priority queue vào đầu tệp C++. 

Chúng ta tạo hàng đợi ưu tiên giống như các vùng chứa khác đã học.

priority_queue<int> integers;

Tiếp theo, chúng ta dùng phương thức push() để thêm phần tử mới vào hàng đợi. Phần tử sẽ được thêm vào. Nếu nó lớn hơn tất cả các phần tử khác, nó sẽ được lưu ở đầu hàng đợi. Nếu nó nhỏ hơn tất cả các phần tử khác, nó sẽ được lưu ở cuối hàng đợi, và cứ thế tiếp tục.

integers.push(5);  // integers = {5)

Để xuất các phần tử, chúng ta dùng phương thức top() như với ngăn xếp. Phương thức này xuất phần tử có mức độ ưu tiên cao nhất. Với các số nguyên, phần tử đó là số lớn nhất.

integers.push(100);  // integers = {100, 5}
integers.push(10);  // integers = {100, 10, 5}
integers.push(3);  // integers = {100, 10, 5, 3}
cout << integers.top();

Output:
100

Chúng ta cũng xóa phần tử giống như với ngăn xếp, bằng phương thức pop(). Phương thức này xóa phần tử ở đầu hàng đợi, tức phần tử có mức độ ưu tiên cao nhất. Với các số, đó là số lớn nhất.

integers.pop();  // integers = {10, 5, 3}
cout << integers.top();

Output:
10

Chúng ta có thể thay đổi mức độ ưu tiên của hàng đợi, từ đó thay đổi thứ tự sắp xếp các phần tử. Ví dụ, chúng ta có thể khai báo hàng đợi ưu tiên sắp xếp các số nguyên theo thứ tự tăng dần như sau:

priority_queue<int, vector<int>, greater<int> > integers;

Trong hàng đợi này, các phần tử được sắp xếp theo thứ tự tăng dần khi được thêm vào. Khi muốn hiển thị phần tử ở đầu hàng đợi hoặc xóa phần tử đó bằng phương thức pop(), số nhỏ nhất sẽ được hiển thị hoặc xóa.

Hiện tại, bạn chưa cần quan tâm đến cách sử dụng hàng đợi ưu tiên khác đi hay thay đổi mức độ ưu tiên. Chỉ cần nhớ rằng chúng ta có thể sử dụng cấu trúc dữ liệu này để sắp xếp các phần tử dựa trên một mức độ ưu tiên nào đó.

Các phương thức của hàng đợi ưu tiên