FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Java]要素と優先度をあわせて追加できる優先度付きキュー

JDKに用意されている優先度つきキュー(PriorityQueue)って、
要素を追加するときに優先度を設定できないんですよね。

// こうはできない。
PriorityQueue<String> queue = new PriorityQueue<String>();
queue.offer("最優先", 1);
queue.offer("ちょい優先", 2);
ってことで、こういうことができるクラス SettablePriorityQueue を作りました。

サンプルコード

こんな感じで使えます。
後から優先度を更新することもできるようになってます。
SettablePriorityQueue<String, Integer> solveOrderQueue
= new SettablePriorityQueue<String, Integer>();

solveOrderQueue.offer("簡単な問題", 5);
solveOrderQueue.offer("普通の問題", 6);
solveOrderQueue.offer("難しい問題", 7);

System.out.println(solveOrderQueue); // -> [簡単な問題, 普通の問題, 難しい問題]

// 優先度の更新
solveOrderQueue.updatePriority("難しい問題", 1);

System.out.println(solveOrderQueue); // -> [難しい問題, 普通の問題, 簡単な問題]

// getPriorityで要素の優先度を取得できます
System.out.println(solveOrderQueue.getPriority("簡単な問題")); // -> 5
System.out.println(solveOrderQueue.getPriority("普通の問題")); // -> 6
System.out.println(solveOrderQueue.getPriority("難しい問題")); // -> 1
Queueインタフェースを実装しているので、Queueのメソッドはすべて使うことができます。

ダウンロード

ソースコードがGistにあるので、そこからコピーするかダウンロードしてください。
(テストコードはこちら)。

型パラメータについて

newする際、1番目の型パラメータには、要素の型を指定します。
また2番目の型パラメータには、優先度を表すオブジェクトの型を指定します。
この型はComparableを実装している必要があります。SettablePriorityQueue<要素の型, 優先度を表すオブジェクトの型>

要素の順序付けに関する細かな仕様

要素のみを追加するoffer(E)と、優先度つきで要素を追加するoffer(E, Priority)を両方使った場合、
要素の順序付けは要素自身の自然順序付けに従います。
つまりoffer(E, Priority)で指定した優先度は無視されます。
要素すべてに対して優先度が設定された場合に限り優先度に従った順序付けが行わます。
通常このクラスを使用する場合、要素と優先度は同時に指定したいはずですので、
このことはあまり気にする必要はないでしょう。
(要素だけ追加するならPriorityQueueを使えばいい話ですので)SettablePriorityQueue<Integer, Integer> queue
= new SettablePriorityQueue<Integer, Integer>();

// 要素だけを追加
queue.offer(2);
queue.offer(1);
queue.offer(3);

System.out.println(queue); // -> [1, 2, 3] 順序は要素の自然順序付けに従う

// 要素だけの追加と、優先度つき要素の追加を混合
queue.clear();
queue.offer(2);
queue.offer(1, 0);
queue.offer(3);
queue.offer(4, 1);

System.out.println(queue); // -> [1, 2, 3, 4] これも順序は要素の自然順序付けに従う

// 優先度が設定されていない要素に優先度を設定
// (すべての要素に対し優先度が設定された状態にする)
queue.updatePriority(2, 3);
queue.updatePriority(3, 2);

System.out.println(queue); // -> [1, 4, 3, 2] 順序は設定した優先度の順序付けに従う

どんな時に使うの?

ダイクストラ法で最短経路を求める場合なんかに使うといいんじゃあないでしょうか。
関連記事
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

Kenji Suzuki

Author:Kenji Suzuki
IT技術に関するあれこれを書いているブログです。
Pujohead Softの方では開発したソフトを公開しています。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
タグ

プログラミング デザインパターン コードリーディング bat 

検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
メールフォーム

名前:
メール:
件名:
本文:

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。