Hàng đợi ưu tiên trong C ++

Như chúng ta biết rằng cấu trúc dữ liệu hàng đợi là cấu trúc dữ liệu First in First Out. Hàng đợi cũng có một số biến thể. Đây là hàng đợi và hàng đợi ưu tiên.

Ở đây chúng ta sẽ thấy một biến thể của hàng đợi, đó là hàng đợi ưu tiên. Trong cấu trúc này, mỗi phần tử trong hàng đợi có mức độ ưu tiên riêng. Khi chúng tôi chèn mục vào hàng đợi, chúng tôi phải gán giá trị ưu tiên với nó. Nó sẽ xóa phần tử ưu tiên cao nhất lúc đầu. Để triển khai hàng đợi ưu tiên, một trong những phương pháp đơn giản nhất là sử dụng cấu trúc dữ liệu heap.

Hãy để chúng tôi xem một mã C ++ cho STL hàng đợi ưu tiên. Ở đây mức độ ưu tiên được chỉ định dựa trên giá trị. Vì vậy, giá trị cao hơn sẽ được coi là phần tử có mức độ ưu tiên cao nhất.

Thuật toán

insert(key, priority):
Begin
   insert key at the end of the heap
   heapify the array based on the priority
End
delete():
Begin
   item := root element
   root := last element from array
   heapify the array to arrange based on priority
   return item
End

Ví dụ

#include <iostream>
#include <queue>
using namespace std;
void dequeElements(priority_queue <int> que) {
   priority_queue <int> q = que;
   while(!q.empty()){
      cout << q.top() << " ";
      q.pop();
   }
   cout << endl;
}
int main() {
   priority_queue <int> que;
   que.push(10);
   que.push(20);
   que.push(30);
   que.push(5);
   que.push(1);
   cout << "Currently que is holding : ";
   dequeElements(que);
   cout << "Size of queue : " << que.size() << endl;
   cout << "Element at top position : " << que.top() << endl;
   cout << "Delete from queue : ";
   que.pop();
   dequeElements(que);
   cout << "Delete from queue : ";
   que.pop();
   dequeElements(que);
}

Đầu ra

Currently que is holding : 30 20 10 5 1
Size of queue : 5
Element at top position : 30
Delete from queue : 20 10 5 1
Delete from queue : 10 5 1