Hàng đợi ưu tiên là một kiểu dữ liệu trừu tượng để lưu trữ tập hợp các phần tử được ưu tiên hỗ trợ việc chèn và xóa một phần tử dựa trên mức độ ưu tiên của chúng, nghĩa là phần tử có mức độ ưu tiên đầu tiên có thể bị xóa bất kỳ lúc nào. Hàng đợi ưu tiên không lưu trữ các phần tử theo kiểu tuyến tính liên quan đến vị trí của chúng như trong Ngăn xếp, Hàng đợi, Danh sách, v.v. Hàng đợi ưu tiên ADT (kiểu dữ liệu trừu tượng) lưu trữ các phần tử dựa trên mức độ ưu tiên của chúng.
Hàng đợi ưu tiên hỗ trợ các chức năng sau -
Kích thước () - nó được sử dụng để tính toán kích thước của hàng đợi ưu tiên vì nó trả về số phần tử trong đó.
Rỗng () - nó trả về true nếu Hàng đợi ưu tiên trống và false nếu ngược lại
Chèn (phần tử) - được sử dụng để chèn phần tử mới vào Hàng đợi Ưu tiên
Tối thiểu () - nó trả về phần tử có giá trị khóa liên quan nhỏ nhất và hiển thị thông báo lỗi nếu Hàng đợi ưu tiên trống.
removeMin () - nó loại bỏ phần tử được tham chiếu bởi hàm min ().
Nhiệm vụ là triển khai khái niệm hàng đợi ưu tiên của các cặp trong C ++ được sắp xếp theo thứ tự đầu tiên.
Chúng ta có thể giải quyết vấn đề theo kiểu đống tương tự, có hai cách để giải quyết vấn đề
- Mức độ ưu tiên tối đa hoặc Khối lượng lớn nhất
- Mức độ ưu tiên tối thiểu hoặc Min heap
Heap là một cấu trúc cây, trong đó các nút được sắp xếp theo một thứ tự cụ thể. Có hai loại heap Min heap và Max heap. Trong Min heap, nút gốc hoặc nút cha nhỏ hơn nút con của nó, trong khi trong Max heap, nút gốc hoặc nút cha lớn hơn nút con của nó.
Ví dụ
Input: priorityq.push(make_pair(18, 200)) Input: priorityq.push(make_pair(18, 200)) priorityq.push(make_pair(29, 100)) priorityq.push(make_pair(11, 400)) Output: 29 100 Input: priorityq.push(make_pair(10, 200)) priorityq.push(make_pair(20, 100)) priorityq.push(make_pair(19, 400)) Output: 20 100 Through Max priority (Max heap)
Thuật toán
Start Step 1-> In main function() Define priority_queue<pair<int, int> > priorityq Call priorityq.push(make_pair(18, 200)) Call priorityq.push(make_pair(29, 100)) Call priorityq.push(make_pair(11, 400)) Set pair<int, int> top = priorityq.top() Print top.first and top.second Stop
Ví dụ
#include <bits/stdc++.h>
using namespace std;
// main program
int main() {
priority_queue<pair<int, int> > priorityq;
priorityq.push(make_pair(18, 200));
priorityq.push(make_pair(29, 100));
priorityq.push(make_pair(11, 400));
pair<int, int> top = priorityq.top();
cout << top.first << " " << top.second;
return 0;
} Đầu ra
29 100
Thông qua mức độ ưu tiên tối thiểu (Min heap)
Thuật toán
Start Step 1-> In main function() Define priority_queue<pair<int, int> > priorityq Call pq.push(make_pair(10, 200)) Call pq.push(make_pair(20, 100)) Call pq.push(make_pair(15, 400)) Set pair<int, int> top = pq.top() Print top.first and top.second Stop
Ví dụ
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
// main program
int main() {
priority_queue<pi, vector<pi>, greater<pi> > pq;
pq.push(make_pair(10, 200));
pq.push(make_pair(20, 100));
pq.push(make_pair(15, 400));
pair<int, int> top = pq.top();
cout << top.first << " " << top.second;
return 0;
} Đầu ra
10 200