• このエントリーをはてなブックマークに追加

スポンサードリンク

はじめに

優先順位付きキューのを PriorityQueue という. キューの中で最大 (最小) のものを抜き出す場合などに利用する.

1 年前は C++ で書いた

思いかえせば一年前, C++ で PriorityQueue の記事を書いた.

また, 1 年前の coursera の講義で, 自前で PriorityQueue の実装をした.

参考にした java コード:

使い方

Java では, 以下のライブラリを利用する.

宣言

優先順位は,いかの 2 つ指定方法がある.

  • 自然順位づけ
  • 自分で順位をつける

デフォルトでは小さい順で 取り出される.

import java.util.PriorityQueue;

関数

要素を追加する

pq.add (1);

先頭の要素を取り出す

最大 (または最小) の先頭を取り出します.

pq.poll ();

要素を調べる

// キューがからかどうかを調べる
pq.isEmpty ();

// 要素数をしらべる
pq.size ();

Sample

import java.util.PriorityQueue;

public class PriorityQueueSample {
	public static void main (String[] args) {

		// 宣言
		PriorityQueue pq = new PriorityQueue ();

		// 挿入
		pq.add (2);				
		pq.add (3);		
		pq.add (1);

		// 先頭の要素を取り出す
		System.out.println (pq.poll ());

		// キューがからかどうかを調べる
		System.out.println (pq.isEmpty ());		

		// 要素数をしらべる
		System.out.println (pq.size ());													 
	}
}

独自定義の順位づけ

Comparator を実装し, PriorityQueue 生成時に引数で渡す.

import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueSample {
	public static void main (String[] args) {

		// 宣言
		PriorityQueue pq = new PriorityQueue (3, new MyComparator ());

		// 挿入
		pq.add (2);				
		pq.add (3);		
		pq.add (1);

		// 先頭の要素を取り出す
		System.out.println (pq.poll ());
		System.out.println (pq.poll ());
		System.out.println (pq.poll ());		
	}
}
 
class MyComparator implements Comparator {
	@Override
	public int compare (Object arg0, Object arg1) {
		int x = (int) arg0;
		int y = (int) arg1;
		
		if (x < y) {
			return 1;
		} else if (x > y) {
			return -1;
		} else{
			return 0;
		}
	}
}

Iterator の注意

これだと, 1, 3, 2 という順番で出力される.

PriorityQueue は, 取り出すときに優先順位ごとにとりだされるので, Iterator でまわしても, 順番どおりにならない.

import java.util.PriorityQueue;

public class PriorityQueueSample {
	public static void main (String[] args) {

		PriorityQueue pq = new PriorityQueue ();

		pq.add (2);				
		pq.add (3);		
		pq.add (1);

		for (Object i: pq) {
			System.out.println (i);
		}
	}
}