Priority Queue
順位キュー, 優先度付きキュー
Outline
順位キューは、データとキーを保持するデータ構造である.
このデータ構造は、コンピュータのジョブ割り当てや
事象駆動(event-driven)のシミュレータなどで利用されている.
順位キューはStack?やQueue?を一般化したデータ構造であると考えられる.
順位キューには、以下のような操作が考えられる.
- insert : 新しく要素を挿入する.
- extract_max : 最大要素を削除し、それを返す.
これらの操作を簡単に実現するために、順位キューはHeap?を用いて
実装すると簡単である.
ここでは、Heap?で示した自作クラスに
上記の操作を加えることで順位キューを実現している.
Program
class PriorityQueue {
private:
int data[_PQ_MAX];
int size; // 配列heap中のヒープ要素のサイズ
public:
PriorityQueue() {
size = 0;
}
int parent(int i) {
if(i == 0) {
return -1;
}
return i / 2;
}
int left(int i) {
if(2 * i >= size) {
return -1;
}
return 2 * i;
}
int right(int i) {
if(2 * i + 1 >= size) {
return -1;
}
return 2 * i + 1;
}
// ヒープ条件を保持する
void heapify(int i) {
int m = i; // max element index
int l = left(i);
int r = right(i);
if(l != -1) {
m = (data[l] > data[i]) ? l : i;
}
if(r != -1) {
m = (data[m] > data[r]) ? m : r;
}
if(m != i) {
swap(data[i], data[m]);
heapify(m);
}
}
void insert(int key) {
int index = size;
size++;
while(index > 0 && data[parent(index)] < key) {
data[index] = data[parent(index)];
index = parent(index);
}
data[index] = key;
}
int extract_max() {
if(size < 0) {
// under flow
return -1;
}
int max = data[0];
data[0] = data[size - 1];
size--;
heapify(0);
return max;
}
};