Priority Queue 소스 코드 분석

Priority Queue 는 JDK 1.5 부터 제공 하 는 새로운 데이터 구조 인터페이스 로 기반 입 니 다.
우선 순위 더미 의 최대 우선 순위 대기 열.우선 순위 대기 열 은 먼저 대기 열 을 나 가 는 다른 대기 열 과 다르다.매번 대기 열 에서 꺼 내 는 것 은 최고 우선권 을 가 진 요소 이다.Comparator 를 제공 하지 않 으 면 우선 대기 열 에 있 는 요 소 는 기본적으로 자연 순서대로 배열 되 어 있 습 니 다. 즉, 숫자 는 기본적으로 작은 대기 열 에 있 고 문자열 은 사전 순서에 따라 배열 되 며 Comparator 에 따라 지정 할 수 있 습 니 다. 이것 은 어떤 구조 방법 을 사용 하 느 냐 에 달 려 있 습 니 다.우선 순위 대기 열 에 서 는 null 요 소 를 허용 하지 않 습 니 다.자연 정렬 에 의존 하 는 우선 순위 대기 열 은 비교 할 수 없 는 대상 을 삽입 할 수 없습니다. (이렇게 하면 ClassCastException 을 초래 할 수 있 습 니 다)
우선 순위 대기 열 은 무한 하지만 내부 용량 이 있어 대기 열 요 소 를 저장 하 는 배열 크기 를 제어 합 니 다.그것 은 보통 적어도 대열 의 크기 와 같다.우선 순위 대기 열 에 요 소 를 계속 추가 하면 서 용량 이 자동 으로 증가 합 니 다.용량 증가 정책 의 세부 사항 을 지정 할 필요 가 없습니다.
우 리 는 소스 코드 의 측면 에서 Priority Queue 가 어떻게 실현 되 었 는 지 보 자.
쌓 기:
Priority Queue 내부 의 배열 설명 은 다음 과 같 습 니 다.

 private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
 private transient Object[] queue;

우 리 는 queue 앞에서 키워드 transient 를 사용 한 것 을 발 견 했 습 니 다. 왜 일 까요?Priority Queue 의 기본 길 이 는 11 이 고 Priority Queue 는 확 대 됩 니 다

    /**
     * Increases the capacity of the array.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    

그래서 대부분의 경우 실제 데이터 의 크기 는 배열 의 quue 실제 크기 보다 작 습 니 다. 전체 quue 를 직렬 화하 면 낭비 하 는 공간 이 많 습 니 다.그래서 Priority Queue 는 스스로 writeObject 와 readObject 를 실현 하여 성능 을 향상 시 켰 다.(대상 의 서열 화 에 대해 서 는 여 기 를 보십시오)
Priority Queue 초기 화 과정 은 가장 많은 쌓 기 과정 과 대체적으로 같 습 니 다.이 과정 도 hepify 라 고 합 니 다.
물론 기 존 데 이 터 를 Priority Queue 로 바 꾸 려 면 쌓 아야 합 니 다. 빈 Priority Queue 에 새 요 소 를 추가 할 때 만 조정 하 는 과정 입 니 다.

     /**
     * Creates a {@code PriorityQueue} containing the elements in the
     * specified collection.  If the specified collection is an instance of
     * a {@link SortedSet} or is another {@code PriorityQueue}, this
     * priority queue will be ordered according to the same ordering.
     * Otherwise, this priority queue will be ordered according to the
     * {@linkplain Comparable natural ordering} of its elements.
     *
     * @param  c the collection whose elements are to be placed
     *         into this priority queue
     * @throws ClassCastException if elements of the specified collection
     *         cannot be compared to one another according to the priority
     *         queue's ordering
     * @throws NullPointerException if the specified collection or any
     *         of its elements are null
     */
    @SuppressWarnings("unchecked")
    public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }

Priority Queue 는 Collection 형식 을 직접 변환 하 는 것 을 지원 합 니 다.
PriorityQueue。
쌓 기 과정:

private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

새로운 요 소 를 추가 하 는 과정 은 다음 과 같 습 니 다.

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

매번 새로운 요 소 를 추가 할 때마다 실제로는 배열 의 맨 뒤에 증가한다.이 요 소 를 증가 시 킬 때 배열 의 길 이 를 판단 하고 조정 하 는 일련의 동작 이 있다.이 동작 들 이 조정 되면 siftUp 방법 을 조정 해 야 합 니 다.이렇게 하 는 것 은 원래 의 성질 을 보증 하기 위해 서 이다.
기타:
1. 이 실현 은 동기 화 된 것 이 아니다.스 레 드 안전 이 아 닙 니 다.여러 스 레 드 의 임의의 스 레 드 가 구조 적 으로 목록 을 수정 했다 면 이 스 레 드 는 Priority Queue 인 스 턴 스 를 동시에 방문 해 서 는 안 됩 니 다. 이 때 스 레 드 가 안전 한 Priority BlockingQueue 류 를 사용 하 십시오.
2. 이 는 offer, poll, add 방법 에 O (logn) 시간 을 제공 합 니 다.reove (Object) 와 contains (Object) 방법 에 O (n) 시간 을 제공 합 니 다.검색 방법 (peek, element, size) 에 O (1) 를 제공 합 니 다.
3. 방법 iterator () 에서 제공 하 는 교체 기 는 우선 순위 대기 열 에 있 는 요 소 를 질서 있 게 옮 겨 다 니 는 것 을 보장 하지 않 습 니 다.최소 더 미 는 뿌리 결점 이 가장 작 을 뿐 전체 가 질서 가 있다 는 것 을 보장 할 수 없 기 때문이다.
Reference： 1. http://cuisuqiang.iteye.com/blog/2019157
2. http://shmilyaw-hotmail-com.iteye.com/blog/1827136
3. http://zhidao.baidu.com/link?url=jJlf0fLjuv6Y0OjvvQqLo46PhAMdVTHau9NkmHpBYgDBDAtlBnUJrtUfDxS22ftpeR9su6m6n85K6X8W7FpvO_