Java での優先順位付きキューの使い方まとめ (PriorityQueue)

    はじめに

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