優先順位付き待ち行列（Priority queue）(2007/07/23(月) 22:58:42)

優先順位付き待ち行列（Priority queue）とは、普通の待ち行列（キュー）と少し違い、デキュー（取り出す）ときに優先順位の高い（低い）ものから取り出す待ち行列。

順次にデータが出てくる場合においてデータをソートしたい場合において、並び替えを行う時にも有効な手段だと思う（汗

実現方法

２分ヒープのデータ構造を用いており、データの追加/削除がO(log n)で行えるのが特徴。添付しているソースでは一次元配列で実現している。

配列番号0が根として
ある配列番号iにおける左側の子はi * 2
右側の子はi * 2 + 1で表す。
ある配列番号iにおける親はi / 2で表す。

また、ヒープは親要素が常に2つの子要素より大きい（またはその逆）の条件を満たさなければならない。（注：２分探索木ではない）

エンキュー（追加）

データの追加は配列の末尾に行い、実現方法で示した方法で追加した値が、親の値より大きい間値と交換する。

デキュー（取り出し）

取り出すデータは配列の先頭（根）。その後根の値を削除するには、配列の末尾の値を根に代入し、ヒープの条件を満たすように、子の値より小さい間値を交換する。

ソース

#include <iostream>
#include <iomanip>
using namespace std;

template <typename  T, int D>
class PriorityQueue{
public:
  PriorityQueue(){
    data = new T[1 << D];
    index = 0;
  }

  ~PriorityQueue(){
    delete data;
  }

  int size(){
    return index;
  }

  void enqueue(T d){
    int i = index, j;
    T tmp;

    data[index++] = d;
    while(i > 0){
      j = i / 2;
      if(data[i] > data[j]){
        tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
        i = j;
      }
      else break;
    }
  }

  T dequeue(){
    T re = data[0];
    int i = 0, j;
    T tmp;

    data[0] = data[--index];
    while(index > i * 2){
      j = i * 2;
      if(data[j] < data[j + 1])j++;
      if(data[i] < data[j]){
        tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
        i = j;
      }
      else break;
    }
    return re;
  }

  void show(){
    for(int i = 1, j = 0; j < index; i *= 2){
      for(int k = 0; j < index && k < i; j++, k++){
        cout << setw(3) << data[j] << " ";
      }
      cout << endl;
    }
  }

private:
  T *data;
  int index;
};

参考

STLのページ