C++の優先キュー

キューのデータ構造は先入れ先出しのデータ構造であることがわかっています。キューにもいくつかのバリエーションがあります。これらは、デキューと優先キューです。

ここでは、キューの1つのバリエーション、つまり優先キューを確認します。この構造では、キュー内の各要素に独自の優先順位があります。アイテムをキューに挿入するときは、優先度の値を割り当てる必要があります。最初に最も優先度の高い要素を削除します。優先キューを実装する最も簡単な方法の1つは、ヒープデータ構造を使用することです。

優先キューSTLの1つの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