ヒープで優先順位付きキューを実装

データ構造の基礎復習メモ。優先順位付きキューをヒープで実装。pushしてpopすると最小値が取り出されるもの。

追加も削除もO(log(N))

public class PQ {
    protected final static int MAX_SIZE = 32;
    protected int[] heap = new int[MAX_SIZE + 1];
    protected int size = 0;

    private static final void swap(int[] x, int i, int j) {
        int t = x[i];
        x[i] = x[j];
        x[j] = t;
    }

    public void push(int x) {
        int i = ++size; // 0番目は使わない
        heap[i] = x;
        for (int p = i / 2 /* 親 */; p > 0; i = p, p /= 2) {
            // 最後尾から親の方が大きいものと入れ替えていく
            if (heap[p] <= heap[i]) {
                // 親の方が小さくなったら終了
                break;
            } else {
                swap(heap, p, i);
            }
        }
    }

    public int pop() {
        int x = heap[1];
        int i = size--;
        heap[1] = heap[i]; // 最後尾の要素を先頭に
        heap[i] = 0;
        for (int c = 1;;) {
            // 先頭から子の方が大きいものを入れ替えていく
            int l = 2 * c; // 左の子
            int r = 2 * c + 1; // 右の子
            if (l >= i || r >= i) {
                break;
            }
            if (heap[l] <= heap[r]) {
                if (heap[c] <= heap[l]) {
                    // 子の方が大きくなったら終了
                    break;
                } else {
                    swap(heap, l, c); // より小さい方と交換
                    c = l;
                }
            } else {
                if (heap[c] <= heap[r]) {
                    // 子の方が大きくなったら終了
                    break;
                } else {
                    swap(heap, r, c);
                    c = r;
                }
            }
        }
        return x;
    }

    public boolean isEmpty() {
        return size <= 0;
    }

    public static void main(String[] args) {
        PQ pq = new PQ();
        pq.push(1);
        pq.push(4);
        pq.push(7);
        pq.push(5);
        pq.push(6);
        pq.push(8);
        pq.push(2);
        pq.push(9);
        pq.push(3);

        while (!pq.isEmpty()) {
            System.out.println(pq.pop());
        }
    }
}

実行結果

ちゃんと使いたい場合はjava.util.PriorityQueueを使えばおk

IK.AM

ヒープで優先順位付きキューを実装