はじめに

優先順位付きキューのを 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);
        }
    }
}

Special Thanks