C++의 우선 순위 큐

큐 데이터 구조는 선입선출 데이터 구조라는 것을 알고 있습니다. 대기열에도 약간의 변형이 있습니다. Dequeue 및 Priority Queue입니다.

여기에서 대기열의 한 변형, 즉 우선 순위 대기열을 볼 수 있습니다. 이 구조에서 대기열의 각 요소에는 고유한 우선 순위가 있습니다. 대기열에 항목을 삽입할 때 우선 순위 값을 할당해야 합니다. 우선 순위가 가장 높은 요소를 먼저 삭제합니다. 우선순위 큐를 구현하는 가장 쉬운 방법 중 하나는 힙 데이터 구조를 사용하는 것입니다.

우선 순위 큐 STL에 대한 하나의 C++ 코드를 살펴보겠습니다. 여기서 우선 순위는 값을 기반으로 할당됩니다. 따라서 값이 높을수록 우선 순위가 가장 높은 요소로 처리됩니다.

알고리즘

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

예시

#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);
}

출력

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