優先度付きキューをヒープを使って実装します。標準ライブラリに入っていますが、勉強するために自分でやってみました。最後に標準ライブラリの優先度付きキューの使い方も見てみます。

目標

実装を通して優先度付きキューを理解する。
標準ライブラリを使ってみる

優先度付きキューとは

キューは先に入れたものから順に取り出されるような（FIFO）データ構造です。優先度付きキューは、キーと値をセットにして保持し、キーを基準としてある一定の優先順位をつけてデータを取り出します。例えば、キーの大きい要素を優先して取り出すmax-優先度付きキューがあります。

実装する

max-優先度付きキューを実装してみます。なお、要素の値を非負整数とし、値そのものがキーとなるものとします。実装する機能は次の２つです。

push(k)：値kの要素を挿入する
pop()：最大のキーを持つ要素を返して削除する

max-ヒープを利用します。要素を挿入したら二分探索木によって適切な位置に配置し、取り出すときは配列の先頭の要素を取り出せばよいことになります。なお、ヒープの実体である配列は1-originとします。

考え方

push関数

まず、配列の末尾に要素を加え、それから適切な位置に移動していきます。値の大きさを親と比較し、親よりも大きいのであれば交換していきます。これによってmax-ヒープ条件を保つように要素を挿入できます。

pop関数

まず先頭の値をmax_valueに格納した後、末尾の要素を先頭（すなわち根）に移動します。その後、max_heapify関数を根に適用することによって、max-heap条件を保つようにします。max-heapify関数は、与えられたノードiとその左右の子のキーの大きさを比較し、最も大きいものがiでなければそれとiを交換します。交換が起こった場合は自身を再帰的に呼び出し、下の階層へとmax-heap条件の適用を続けます。

ソースコード

priority_queue.h

#ifndef _PRIORITY_QUEUE_
#define _PRIORITY_QUEUE_

class PriorityQueue {
private:
  int size;
  int queue[2000000];

  void max_heapify(int i);  // max-ヒープ条件を適用する
  
public:
  PriorityQueue ();  
  void push(int key);
  int pop();
};

#endif

priority_queue.cpp

#include "priority_queue.h"
#include<iostream>
#include<utility>
using namespace std;

PriorityQueue::PriorityQueue () : size(0) {}
  

void PriorityQueue::max_heapify(int i) {
  int l, r, largest;

  l = i * 2;
  r = i * 2 + 1;

  // largestを決める
  if (l <= size && queue[l] > queue[i]) largest = l;
  else largest = i;    
  if (r <= size && queue[r] > queue[largest]) largest = r;

  if (largest != i) {
    swap(queue[i], queue[largest]);
    max_heapify(largest);
  }
}

void PriorityQueue::push(int key) {
  int parent, pos;
    
  pos = ++size;
  queue[pos] = key;  // 要素を挿入
  // 適切な位置に配置する
  parent = pos / 2;
  while (pos > 1 && queue[pos] > queue[parent]) {
    swap(queue[pos], queue[parent]);
    pos = parent;
    parent = pos / 2;
  }
}

int PriorityQueue::pop() {
  if (size < 1) return -1;

  int max_value = queue[1];

  // 末尾の値を根に配置した後、要素を適切に配置する
  queue[1] = queue[size--];
  max_heapify(1);

  return max_value;
}

main.cpp

#include<iostream>
#include "priority_queue.h"
using namespace std;

int main() {
  PriorityQueue q;

  q.push(1);
  q.push(3);
  q.push(5);

  cout << q.pop() << endl;  // 5

  q.push(2);

  cout << q.pop() << endl;  // 3
  
  return 0;
}

実行結果

5
3

標準ライブラリ

STLで提供されているコンテナpriority_queueの使い方を見てみます。

以下のメンバ関数が定義されています。

push()：要素を挿入する
pop() ：優先度最大の要素を削除する
top() ：優先度最大の要素を返す

int型の場合、デフォルトでは優先度は大きさとなっています。

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

int main() {
  priority_queue<int> q;

  q.push(1);
  q.push(3);
  q.push(5);

  cout << q.top() << endl;  // 5

  q.pop();

  cout << q.top() << endl;  // 3
 
  return 0;
}