目的
D言語でプライオリティキューってどう利用するのかな～って調べたときにQiita上での記事が少なく,
Google検索ではD言語でプライオリティキューは使えませんよっていう古い記事がヒットしたりする.
そこで, 今はあるみたいだよ～って書いておきます.
コンパイラ DMD64 D Compiler v2.095.0
Sample
結論, 以下のプログラムを記述すれば終わりです.
import std.container;
void main() {
auto maxHeap = heapify([1, 2, 3, 4, 5]); // 優先度が高い順
auto minHeap = heapify!"a>b"([1, 2, 3, 4, 5]); // 優先度が低い順
}
D言語でのプライオリティキュー
公式リファレンスでは
This module provides a BinaryHeap (aka priority queue) adaptor that makes a binary heap out of any user-provided random-access range.
This module is a submodule of std.container.
とあるようにプライオリティキューはBinaryHeapとして実装されており, "std.container" をインポートすることで利用できます.
また, 応用の項に詳しく書きますがタプルや構造体を渡しても楽に優先度を決定し利用することができます.
基本操作
公式リファレンスを見れば一発なので不要かとも思いましたが, せっかくなので載せておきます.
適当な基本操作のプログラム
- プライオリティキューの作成
import std.container;
import std.stdio;
void main() {
int[] a = [1, 2, 3, 4, 5, 6];
auto maxHeap = heapify(a);
}
- プライオリティキューに追加
import std.container;
import std.stdio;
void main() {
int[] a = [1, 2, 3, 5, 6];
auto maxHeap = heapify(a);
maxHeap.insert(4);
maxHeap.writeln;
}
- プライオリティキューから先頭を取り除き, それを返す
import std.container;
import std.stdio;
void main() {
int[] a = [1, 2, 3, 4, 5, 6];
auto maxHeap = heapify(a);
maxHeap.removeAny.writeln; // 取り出した結果を出力
}
- 先頭の要素の優先度の変更
import std.container;
import std.stdio;
void main() {
int[] a = [1, 2, 3, 5, 6];
auto maxHeap = heapify(a);
maxHeap.replaceFront(4);
maxHeap.writeln();
}
- 優先度を変更して作成
import std.container;
import std.stdio;
void main() {
int[] a = [1, 2, 3, 5, 6];
auto maxHeap = heapify!"a>b"(a);
maxHeap.writeln;
}
- 先頭から複数の複数の値を取り出す
import std.container;
import std.stdio;
import std.range;
void main() {
int[] a = [1, 2, 3, 4, 5];
auto maxHeap = heapify(a);
auto b = maxHeap.take(3);
b.writeln;
}
AtCoder での利用例
AtCoder 上でのプライオリティキューを使う問題を実装. 他の言語と比較するとわかりやすいと思います.
優先度付きキュー（ヒープ）の使い方で紹介があったABC141を実装.
ABC141-D 提出結果
int N, M;
long[] A;
long solve() {
// 品物をプライオリティキューに入れる
auto maxHeap = heapify(A);
// 割引券の回数だけ品物を高い順に割引していく
foreach(i; 0..M) {
// 一番高い品物の取り出し
long val = maxHeap.removeAny;
// 割引して再代入
maxHeap.insert( val/2 );
}
return maxHeap.sum();
}
void main(){
// 入力部分
inelm(N, M);
A = inarr!long();
// 計算して出力
solve.writeln;
}
import std;
const long mod = 10^^9+7;
const long inf = 10L^^18+1;
alias instr = () => readln.chomp;
T inone(T=int)(){return readln.chomp.to!T;}
void inelm(L...)(ref L A){ auto l = readln.split;
foreach(i, T; L) A[i]=l[i].to!T; }
T[] inarr(T = int)(){ return readln.split.to!(T[]); }
T convert_num(T=int)(char c){ return (c-'0').to!T; }
応用
では, 構造体やタプルを渡してこういうこともできるよね.
import std.range;
import std.container;
import std.stdio;
import std.typecons : Tuple;
alias Tuple!(int, int) P;
void main() {
auto vals = [ P(1,2), P(3,1), P(3,5), P(2,9), P(10,10);
auto maxHeap = heapify!"a[0]+a[1]<b[0]+b[1]"(vals);
maxHeap.take(3).writeln;
}
何がやりたいのかというと, (int, int)型のタプルを渡してやって２つの整数の和を優先度としたキューを作成してほしいというもの.
出力結果は以下
[Tuple!(int, int)(10, 10), Tuple!(int, int)(2, 9), Tuple!(int, int)(3, 5)]
新たに定義した P のタプル型に関してP[0]+P[1]が優先度になっていますね.
じゃあ, 構造体ならどうかというと,
import std.container;
import std.stdio;
struct A{
int a;
int b;
this(int _a, int_b) {
a = _a;
b = _b;
}
}
void main() {
auto a = [A(1,1), A(2,1), A(3, 2)];
auto maxHeap = heapify!"a.a<b.a"(a);
maxHeap.writeln;
}
[A(3,1), A(2,2), A(1,1)]
簡潔に実装できそうですね.
以上.
追記
これまでは, 事前に配列作成してプライオリティキューを作成しましたが型だけ指定した空のプライオリティキューが欲しくなりまして, 以下のエイリアスを追記しました.
詳細については kotet さんのブログ で紹介されています.
import std;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
void main() {
PQueue!(int, "a>b") que;
}
参考
公式リファレンス dlang.org
日本語リファレンスkmonos.net
追記分 blog.kotet.jp