---
title: ヒープで優先順位付きキューを実装
tags: []
categories: ["Programming", "DataStructure", "Heap", "PriorityQueue"]
date: 2011-07-20T17:16:08Z
updated: 2010-07-20T17:16:08Z
---

データ構造の基礎復習メモ。優先順位付きキューをヒープで実装。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());
            }
        }
    }


実行結果

    1
    2
    3
    4
    5
    6
    7
    8
    9


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